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

题面

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

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

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

题意

有一个人有N项工作,给N组数据,每组数据有Ti和Si,分别表示第i组工作需要花费的时间和最晚完成的时间。

初始时间为0,要求算出最晚可以什么时间开始工作。

题解

50分操作 (有BUG 不严谨证明)

由题意可以知道这道题可以尝试以下模拟操作。

  1. 排序每一项最晚完成的时间。

  2. 枚举,如果前i项任务完成时间超过第i项任务花费的时间,就非法,输出-1。

  3. 统计出每一项任务 最晚完成时间 - 花费时间的值。

  4. 排序输出最小的统计值。 (不完全归纳法得出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分的操作上进行严谨的贪心证明。

  1. 排序每一项最晚完成的时间。

  2. 得出最晚完成的时间,并用一个中间变量存储。

  3. 枚举,用中间变量减去每一项所要花费的时间。

  4. 对结果进行判断,如果中间变量小于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;
}
上一篇:更新日志 - BugHD iOS 客户端上线


下一篇:[LUOGU] P2920 [USACO08NOV]时间管理Time Management