首页 > 代码库 > UVA1467 - Installations
UVA1467 - Installations
题目链接
题意:有n个服务,每个服务都有安装时间s,截止时间d。如果任务没有在截止时间之前完成,会有惩罚值,假设完成时间为C,则惩罚值为max(C-d,0)。求最两个最大惩罚值之和的最小值。
思路:我们先按照截止时间d从小到大排序,如果d相同,则s小的排前面。这样处理得到的总的惩罚值是较优解,但不是最优解。排序之后,找到序列中惩罚值最大值和第二大值的两者中比较靠后的位置p,然后从0到p-1中枚举一个d放在p位置后面,d+1到p集体往左移动一位,这样就可以使得最大值和第二大值减小,但并不能保证每次在两个值都减小的过程中,依然保证两个还是最大值和第二大值,有可能牺牲的那个d会取代其中一个,所以要不断更新最小值。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 505; struct task{ int s, d; }t[MAXN]; int n, p; int cmp(task a, task b) { if (a.d != b.d) return a.d < b.d; else return a.s < b.s; } int deal(int x) { int cnt = 0, a = 0, b = 0, temp; for (int i = 0; i <= p; i++) { if (x == i) continue; cnt += t[i].s; temp = max(cnt - t[i].d, 0); if (temp > a) { b = a; a = temp; } else if (temp > b) b = temp; } cnt += t[x].s; temp = max(cnt - t[x].d, 0); if (temp > a) { b = a; a = temp; } else if (temp > b) { b = temp; } return a + b; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &t[i].s, &t[i].d); sort(t, t + n, cmp); int cnt = 0, a = 0, b = 0; for (int i = 0; i < n; i++) { cnt += t[i].s; int temp = max(cnt - t[i].d, 0); if (temp > a) { b = a; a = temp; p = i; } else if (temp > b) { b = temp; p = i; } } int ans = a + b;; for (int i = 0; i < p; i++) ans = min(ans, deal(i)); printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。