首页 > 代码库 > UVa 1467 (贪心+暴力) Installations

UVa 1467 (贪心+暴力) Installations

2024-08-04 05:15:30   220人阅读

题意：

一共有n项服务，每项服务有安装的时间s和截止时间d。对于每项任务，如果有一项超出截止时间，惩罚值为所超出时间的长度。问如何安装才能使惩罚值最大的两个任务的惩罚值之和最小。

分析：

如果是求总惩罚值的最小值，则按所有任务的截止时间排序，这样贪心的理由是，先完成截止时间早的任务至少不会是情况变得更坏。

虽然题目所求不是这个，但我们可以稍作修改。

设p为按上述贪心顺序安装任务，惩罚值最大的两个任务中靠后的那个位置。

枚举p之前的任务i，将第i个任务移到p后面执行，有可能减小两个最大惩罚值之和，所以维护一个最小值即可。

但还有一个问题就是，为什么不可能是移动两个任务到p后面得到最优解？？

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4  5 const int maxn = 500 + 10; 6 int n, p; 7 struct Job 8 { 9     int s, d;10     Job(int s = 0, int d = 0):s(s), d(d) {}11     bool operator < (const Job& a) const12     {13         return d < a.d;14     }15 }job[maxn];16 17 int test(int x)18 {19     int t = 0, a = 0, b = 0, k = 0;20     for(int i = 0; i <= p; ++i)21     {22         if(i == x) continue;23         t += job[i].s;24         k = max(0, t - job[i].d);25         b = max(b, k);26         if(b > a) swap(a, b);27     }28     t += job[x].s;29     k = max(0, t - job[x].d);30     b = max(b, k);31     return a + b;32 }33 34 int main(void)35 {36     //freopen("1467in.txt", "r", stdin);37     int T;38     scanf("%d", &T);39     while(T--)40     {41         scanf("%d", &n);42         for(int i = 0; i < n; ++i)43         {44             int s, d;45             scanf("%d%d", &s, &d);46             job[i] = Job(s, d);47         }48         49         sort(job, job + n);50         int t = 0, a = 0, b = 0;51         for(int i = 0; i < n; ++i)52         {53             t += job[i].s;54             if(t - job[i].d >= b)55             {56                 b = t - job[i].d;57                 p = i;58             }59             if(b > a) swap(a, b);60         }61         62         int ans = a + b;63         for(int i = 0; i < p; ++i)64             ans = min(ans, test(i));65             66         printf("%d\n", ans);67     }68     69     return 0;70 }
代码君

 

UVa 1467 (贪心+暴力) Installations


联系
我们