[USACO08NOV]时间管理Time Management

布满荆棘的人生 2021-11-04 21:58 233阅读 0赞

## 题目描述 ##

作为一名忙碌的商人，约翰知道必须高效地安排他的时间.他有N工作要 做，比如给奶牛挤奶，清洗牛棚，修理栅栏之类的.

为了高效，列出了所有工作的清单.第i分工作需要T\_i单位的时间来完成，而 且必须在S\_i或之前完成.现在是0时刻.约翰做一份工作必须直到做完才能停 止.

所有的商人都喜欢睡懒觉.请帮约翰计算他最迟什么时候开始工作，可以让所有工作按时完成.（如果无法完成全部任务，输出-1）

## 输入输出格式 ##

**输入格式：**

\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains two space-separated integers: T\_i and S\_i

**输出格式：**

\* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.

## 输入输出样例 ##

**输入样例\#1：** 复制

4 3 5 8 14 5 20 
    
    【解题思路】

/如果当前的时间加上任务所需的时间小于等于结束时间，将新的时间等于旧的时间加上任务时间

check函数 【code】

1 #include <cstdio>
     2 #include <iostream>
     3 #include <algorithm>
     4 using namespace std;
     5 int n,l,r,ans;
     6 struct Node{
     7     int s;
     8     int t;
     9 }a[1005];
    10 inline bool cmp(const Node &a,const Node &b){
    11     return a.t<b.t;
    12 }
    13 inline bool check(int mid){
    14     int cnt=mid;
    15     for(register int i=1;i<=n;i++){
    16         if(a[i].s+cnt<=a[i].t)
    17             cnt+=a[i].s;
    18         else return false;
    19     }
    20     return true;
    21 }
    22 int main(){
    23     //freopen("2920.in","r",stdin);
    24     //freopen("2920.out","w",stdout);
    25     scanf("%d",&n);
    26     for(register int i=1;i<=n;i++)
    27         scanf("%d%d",&a[i].s,&a[i].t);
    28     sort(a+1,a+n+1,cmp);
    29     l=1,r=10000000;
    30     while(l<=r){
    31         int mid=(l+r)/2;
    32         if(check(mid)){
    33             ans=mid;
    34             l=mid+1;
    35         }
    36         else r=mid-1;
    37     }
    38     if(ans!=0)printf("%d\n",ans);
    39     else printf("-1\n"); 
    40     return 0;
    41 }

转载于:https://www.cnblogs.com/66dzb/p/11204042.html