UVALive - 3507 Keep the Customer Satisfied

題意：收到n個訂單，每個訂單有q,d分別代表做這個的時間，和最晚的完成時間，問你最多能接受幾個訂單

思路：貪心，我們顯然要按最早的完成時間排序，那麼接下來，我們用（6，8）和（4，9）做為例子，按照我們的貪心原則我們首先選擇（6，8），然後再（4，9），但顯然（4，9）作為首選才是最好的選擇，試想一下不能兩個都選的情況，就是我們總共做的時間4+6>9(第二個的最遲的時間)，那麼我們要刪除做的時間最長的才是最優的

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 1000002;

struct node{
    int q,d;
}arr[MAXN];
int n;

bool cmp(node a,node b){
    return a.d < b.d;
}

int main(){
    int t;
    scanf("%d",&t);
    for (int cas = 0; cas < t; cas++){
        if (cas)
            printf("\n");
        scanf("%d",&n);
        for (int i = 0; i < n; i++)
            scanf("%d%d",&arr[i].q,&arr[i].d);
        sort(arr,arr+n,cmp);
        priority_queue Q;
        int ans = 0;
        for (int i = 0; i < n; i++){
            ans += arr[i].q;
            Q.push(arr[i].q);
            while (ans > arr[i].d){
                ans -= Q.top();
                Q.pop();
            }
        }
        printf("%d\n",Q.size());
    }
    return 0;
}