题面
作为一名忙碌的商人,约翰知道必须高效地安排他的时间.他有N工作要 做,比如给奶牛挤奶,清洗牛棚,修理栅栏之类的.
为了高效,列出了所有工作的清单.第i分工作需要T_i单位的时间来完成,而 且必须在S_i或之前完成.现在是0时刻.约翰做一份工作必须直到做完才能停 止.
所有的商人都喜欢睡懒觉.请帮约翰计算他最迟什么时候开始工作,可以让所有工作按时完成.(如果无法完成全部任务,输出-1)
题意
有一个人有N项工作,给N组数据,每组数据有Ti和Si,分别表示第i组工作需要花费的时间和最晚完成的时间。
初始时间为0,要求算出最晚可以什么时间开始工作。
题解
50分操作 (有BUG 不严谨证明)
由题意可以知道这道题可以尝试以下模拟操作。
排序每一项最晚完成的时间。
枚举,如果前i项任务完成时间超过第i项任务花费的时间,就非法,输出-1。
统计出每一项任务 最晚完成时间 - 花费时间的值。
排序输出最小的统计值。 (不完全归纳法得出3、4操作,不严谨证明)
#include<bits/stdc++.h>
using namespace std;
int n = 0,tong[1010];
struct edge{
int t,s;
bool operator < (const edge &qxq)
{
return s < qxq.s;
}
}num[1010];
int main(int argc, char const *argv[])
{
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> num[i].t >> num[i].s;
if(num[i].t > num[i].s)
{
cout << -1;
return 0;
}
tong[i] = num[i].s - num[i].t;
}
sort(num+1,num+n+1);
sort(tong+1,tong+n+1);
long long sum = 0;
for(int i = 1;i <= n;i++)
{
sum += num[i].t;
if(sum > num[i].s)
{
cout << -1;
return 0;
}
}
cout << tong[1];
return 0;
}
满分做法 AC100
建立在50分的操作上进行严谨的贪心证明。
排序每一项最晚完成的时间。
得出最晚完成的时间,并用一个中间变量存储。
枚举,用中间变量减去每一项所要花费的时间。
对结果进行判断,如果中间变量小于0,非法,输出-1;否则中间变量剩余的时间就是答案,也就是商人最晚起床时间。
#include<bits/stdc++.h>
using namespace std;
int n = 0;
struct edge{
int t,s;
bool operator < (const edge &qxq)
{
return s > qxq.s;
}
}num[1010];
int main(int argc, char const *argv[])
{
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> num[i].t >> num[i].s;
}
sort(num+1,num+n+1);
int ans = num[1].s;
for(int i = 1;i <= n;i++)
{
if(ans <= num[i].s) ans -= num[i].t;
else ans = num[i].s - num[i].t;
}
if(ans < 0) cout << "-1";
else cout << ans;
return 0;
}