uva 1153—— Keep the Customer Satisfied

缺乏、安全感 2022-08-09 16:34 126阅读 0赞

题意：有n个工作，已知每个工作的开始时间和结束时间，问最多能完成多少工作。

思路：贪心。要想使得最后的结果最佳，那么开始的晚的，要在最后来做。在此基础上，需要保证先做开始的早的（需要用优先队列来维护）。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=800010;
    const int M=100;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define fr(i,s,n) for (int i=s;i<=n;i++)
    
    struct node
    {
        int q,d;
    }v[N];
    bool cmp(node a,node b)
    {
        return a.d<b.d;
    }
    int n;
    int sol()
    {
        priority_queue<int>qu;
        int t=0;
        fr(i,1,n)
        {
            if (t+v[i].q<=v[i].d)
            {
                qu.push(v[i].q);
                t+=v[i].q;
            }
            else if (!qu.empty())
            {
                int tp=qu.top();
                if (tp>v[i].q)
                {
                    qu.pop();
                    t=t-tp+v[i].q;
                    qu.push(v[i].q);
                }
            }
        }
        return qu.size();
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d",&n);
            fr(i,1,n) scanf("%d %d",&v[i].q,&v[i].d);
            sort(v+1,v+n+1,cmp);
            printf("%d\n",sol());
            if (T) puts("");
        }
    }