题解 P2920 【[USACO08NOV]时间管理Time Management】

· · 题解

简单的贪心思路：

  1. 对每件事最迟结束时间从大到小排序，该顺序为完成最后一件事到最早一件事
  2. 定义now为所有事件结束时间
  3. 每件事最迟开始时间，与前一件事最迟结束时间比较，如果大于，说明此解不成立，为了维护时间，now赋成该值
  4. 循环完后，如果now<0，与实际不符，说明无解输出-1，否则输出now（此时为最优解，可通过简单推算证明出）

代码如下

# include<cstdio>
# include<algorithm>
using namespace std;
# define max_n 1001
  struct node{
  int pay,late;
}cun[max_n];
bool sort1(node t,node tt){return t.late>tt.late;}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&cun[i].pay,&cun[i].late);
    sort(cun+1,cun+1+n,sort1);//按结束时间从早到晚排序 ,由于求最迟时间,这样排序是最优解的顺序（贪心） 
    int now=cun[1].late;
    for(int i=1;i<=n;++i){
        now=now-cun[i].pay;//结束时间 
        if(i==n){
            if(now<0) printf("-1");else printf("%d",now);
            return 0;//循环到n退出 
        }
        if(now>cun[i+1].late) now=cun[i+1].late;//结束时间大于前一个事件,说明此方式无解需推前时间 
    }
}