6、贪心 &推公式

AcWing 125. 耍杂技的牛

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();

    }

    //    构造大顶堆：
    int N=100010;
    int a[];
    ArrayList<NIU> arrayList=new ArrayList();
    class NIU implements Comparable{
        int w,s;
        public NIU(int w,int s){
            this.w=w;
            this.s=s;
        }

        @Override
        public int compareTo(Object o) {
            NIU niu= (NIU) o;
            return (w+s)-niu.w-niu.s;
        }
    }
    void init() {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            arrayList.add(new NIU(sc.nextInt(),sc.nextInt()));
        }
        Collections.sort(arrayList);
        int res=-0x3f3f3f;
        int sum=0;
        for (int i = 0; i < arrayList.size(); i++) {
            res=Math.max(res,sum-arrayList.get(i).s);
            sum+=arrayList.get(i).w;
        }
        System.out.println(res);
    }
}