51nod1099 贪心

女爷i 2022-07-26 01:50 112阅读 0赞

有N个任务需要执行，第i个任务计算时占R\[i\]个空间，而后会释放一部分，最后储存计算结果需要占据O\[i\]个空间（O\[i\] < R\[i\]）。

例如：执行需要5个空间，最后储存需要2个空间。给出N个任务执行和存储所需的空间，问执行所有任务最少需要多少空间。

题目意思刚开始有点不懂，但是又好像懂了就开始写。然后知道肯定是排序，一开始觉得是按照r排序，r越大越先执行这样看好像是需要的空间最小，但是交了发现不对。

后来改了又改还是不对，然后就意识到应该是贪心的方法不对，不应该用r排序，然后就想到应该是按照r和o的差值排序，这样想的原因是，每次执行一个任务刚开始需要r和空间，但是最终释放之后只需要o和空间，这样不就是每次执行一个任务多了r-o个额外的不需要存储但是却在过程中被占用的空间吗，那么就根据这个被占用的空间贪心就好了。

#include <map>
    #include <queue>
    #include <stack>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std ;
    #define mem(a) memset(a,0,sizeof(a))
    #define inf 100000005
    
    int const maxn = 100005;
    
    struct node
    {
        int r,o;
    }A[maxn];
    
    bool cmp(node a,node b)
    {
        if((a.r-a.o)!=(b.r-b.o))return (a.r-a.o)>(b.r-b.o);
        return a.r>b.r;
    }
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            for(int i = 0 ; i < n ; i++)
            {
                scanf("%d%d",&A[i].r,&A[i].o);
            }
            sort(A,A+n,cmp);
            long long ans = 0 ;
            long long num = 0 ;
            for(int i = 0 ; i < n ; i++)
            {
                num += A[i].r;
                ans = max(num,ans);
                num = num + A[i].o - A[i].r ;
                //ans = max(num,ans);
            }
            printf("%I64d\n",ans);
        }
        return 0 ;
    }