P2920 [USACO08NOV]时间管理Time Management
显然的贪心。
按deadline从大到小排序,然后依次填充时间。
最后时间为负的话那么就是无解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
int max(int a,int b){return a>b?a:b;}
struct data{
int t,dl;
bool operator < (const data &tmp) const{return dl>tmp.dl;}
}a[];
int n,tt,ans;
int main(){
scanf("%d",&n);
for(re int i=;i<=n;++i) scanf("%d%d",&a[i].t,&a[i].dl);
sort(a+,a+n+); tt=a[].dl;
for(re int i=;i<=n;++i){
tt=min(tt,a[i].dl); tt-=a[i].t;//注意在deadline前完成所以要取min
}tt< ? printf("-1"):printf("%d",tt);
return ;
}