CodeForces 3B Lorry

　　原题链接：http://codeforces.com/problemset/problem/3/B

　　看了好久才明白题意：有一辆卡车，要装载一些船只，这些船只分为“1”和“2”两种，再给出n只船的类型及其capacity（理解为“价值”会更好），要求给定卡车容量v的情况下求最大装载价值。

　　理解完题意之后我想是背包问题吧，但是所给v达到10^9。

　　其实这道题用的是贪心思想。

　　首先把两种船只分开，分别进行排序。最优解总是先取价值高的。可以O(n)的时间复杂度枚举选择i只“1”船，则选择“2”船只的个数就是min((v - i) / 2, tc)，tc为“2”船总个数，后面的处理就不难了。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #define FOR(i,s,t) for(int i = (s); i <= (t); i++)
 5 const int maxn = 100000 + 5;
 6 int sum1[maxn], sum2[maxn], oc, tc, ans[maxn];
 7 
 8 struct node
 9 {
10     int id;
11     int val;
12 }one[maxn], two[maxn];
13 
14 bool cmp(node x, node y)
15 {return x.val > y.val;}
16 
17 int main()
18 {
19     int n, v, a, b, maxv, c1, c2;
20     while(scanf("%d%d", &n, &v) != EOF)
21     {
22         oc = tc = 0;
23         FOR(i, 1, n)
24         {
25             scanf("%d%d", &a, &b);
26             if(a == 1)
27                 one[++oc].val = b, one[oc].id = i;
28             else
29                 two[++tc].val = b, two[tc].id = i;
30         }
31         std::sort(one+1, one + oc + 1, cmp);
32         std::sort(two+1, two + tc + 1, cmp);
33         sum2[0] = sum1[0] = 0;
34         FOR(i, 1, tc) sum2[i] = sum2[i - 1] + two[i].val;
35         FOR(i, 1, oc) sum1[i] = sum1[i - 1] + one[i].val;
36         c1 = -1, c2 = -1, maxv = -1;
37         FOR(i, 0, oc)
38         {
39             if(i > v)
40                 break;
41             int d = sum1[i] + sum2[std::min((v - i) / 2, tc)];
42             if(d > maxv)
43             {
44                 maxv = d;
45                 c1 = i;
46                 c2 = std::min((v - i) / 2, tc);
47             }
48         }
49         if(maxv == -1)
50         {
51             puts("0");
52             continue;
53         }
54         int cnt = 0;
55         printf("%d\n", maxv);
56         FOR(i, 1, c1) ans[++cnt] = one[i].id;
57         FOR(i, 1, c2) ans[++cnt] = two[i].id;
58         FOR(i, 1, cnt)
59             printf("%d%c", ans[i], i == cnt? '\n' : ' ');
60     }
61     return 0;
62 }