USACO 之 Section 1.3 Greedy Algorithm （已解决）

Mixing Milk：单价越少，买相同数量的牛奶花费越少。。。先排序，再求解。。。

 1 /*
 2 ID: Jming
 3 PROG: milk
 4 LANG: C++
 5 */
 6 #include <iostream>
 7 #include <cstdlib>
 8 #include <cstdio>
 9 #include <algorithm>
10 using namespace std;
11 int N, M;
12 
13 struct myNode {
14     int P, A;
15 } node[5005];
16 
17 bool Cmp(const myNode &n1, const myNode &n2){
18     if (n1.A == n2.A) return n1.P < n2.P;
19     else return n1.A < n2.A;
20 }
21 
22 void Solve() {
23     int myCost = 0;
24     int myCount = 0;
25     for (int i = 0; i < M; ++i) {
26         if (myCount + node[i].P > N) {
27             myCost += (N-myCount)*node[i].A;
28             break;
29         }else {
30             myCount += node[i].P;
31             myCost += node[i].A*node[i].P;
32         }
33     }
34     printf("%d
", myCost);
35 }
36 
37 int main()
38 {
39     freopen("milk.in", "r", stdin);
40     freopen("milk.out", "w", stdout);
41     scanf("%d %d", &N, &M);
42     for (int i = 0; i < M; ++i) {
43         scanf("%d %d", &node[i].A, &node[i].P);
44     }
45     sort(node, node + M, Cmp);
46     Solve();
47     return 0;
48 }

Barn Repair:

注意：牛所在的牛棚的编号是乱序的，需要先从小到大排序
分情况讨论：
1）M == 1 ：最大的牛棚编号 - 最小的牛棚编号 + 1
2）M >= C : 直接输出 C 即可
3）M < C : 根据各牛棚编号之间的差值，贪心处理（尽量删去差值大的，选取差值小的）

 1 /*
 2 ID: Jming
 3 PROG: barn1
 4 LANG: C++
 5 */
 6 
 7 #include <iostream>
 8 #include <cstdlib>
 9 #include <cstdio>
10 #include <cmath>
11 #include <algorithm>
12 #include <functional>
13 #include <string>
14 #include <cstring>
15 #include <vector>
16 #include <stack>
17 #include <queue>
18 #include <map>
19 using namespace std;
20 #define eps 1e-8
21 #define MAX_C 205
22 
23 int M, S, C;
24 int myArr[MAX_C];
25 vector<int> myVec;
26 
27 struct myNode {
28     int Pos;
29     int Dis;
30 };
31 myNode node[MAX_C];
32 
33 bool Cmp(const myNode n1, const myNode n2) {
34     return n1.Dis > n2.Dis;
35 }
36 
37 void Solve() {
38     int myBegin = 0;
39     int Sum = 0, tmp;
40     myVec.push_back(C-1);
41     for (int i = 0; i < myVec.size(); ++i) {
42         tmp = myArr[myVec[i]] - myArr[myBegin] + 1;
43         if (tmp) Sum += tmp;
44         else ++Sum;
45         myBegin = myVec[i] + 1;
46     }
47     printf("%d
", Sum);
48 }
49 
50 int main() {
51     freopen("barn1.in", "r", stdin);
52     freopen("barn1.out", "w", stdout);
53     scanf("%d %d %d", &M, &S, &C);
54     for (int i = 0; i < C; ++i) {
55         scanf("%d", &myArr[i]);
56     }
57     sort(myArr, myArr + C);
58     for (int i = 1; i < C; ++i) {
59         node[i - 1].Pos = i - 1;
60         node[i - 1].Dis = myArr[i] - myArr[i - 1];
61     }
62     if(M >= C) {
63         printf("%d
", C);
64         return 0;
65     }
66     if (1 == M) {
67         printf("%d
", myArr[C - 1] - myArr[0] + 1);
68         return 0;
69     }
70     sort(node, node + (C - 1), Cmp);
71     for (int i = 0; i < (M - 1); ++i) {
72         myVec.push_back(node[i].Pos);
73     }
74     sort(myVec.begin(), myVec.end());
75     Solve();
76     myVec.clear();
77     return 0;
78 }

Prime Cryptarithm: 穷举即可。。。

 1 /*
 2 ID: Jming
 3 PROG: crypt1
 4 LANG: C++
 5 */
 6 
 7 #include <iostream>
 8 #include <cstdlib>
 9 #include <cstdio>
10 #include <cmath>
11 #include <algorithm>
12 #include <functional>
13 #include <string>
14 #include <cstring>
15 #include <vector>
16 #include <stack>
17 #include <queue>
18 #include <map>
19 using namespace std;
20 #define eps 1e-8
21 int myArr[15];
22 int N;
23 
24 bool myJudge(int x) {
25     while (x) {
26         int tmp1 = x % 10;
27         int i;
28         for (i = 0; i < N; ++i) {
29             if (tmp1 == myArr[i]) {
30                 break;
31             }
32         }
33         if (i == N) {
34             return false;
35         }
36         x /= 10;
37     }
38     return true;
39 }
40 
41 void Solve() {
42     int ans = 0;
43     for (int i = 0; i < N; ++i) {
44         for (int j = 0; j < N; ++j) {
45             for (int k = 0; k < N; ++k) {
46                 int mydata = myArr[i] * 100 + myArr[j] * 10 + myArr[k];
47 
48                 for (int m = 0; m < N; ++m) {
49                     int data1 = mydata * myArr[m];
50                     if (!myJudge(data1)) continue;
51                     if (data1 >= 1000) continue;
52 
53                     for (int n = 0; n < N; ++n) {
54                         int data2 = mydata * myArr[n];
55                         if (!myJudge(data2)) continue;
56                         if (data2 >= 1000) continue;
57                         int myMul = data1 + data2 * 10;
58                         if (!myJudge(myMul)) continue;
59                         if (myMul >= 10000) continue;
60                         ++ans;
61                     }
62                 }
63             }
64         }
65     }
66     printf("%d
", ans);
67 }
68 
69 int main()
70 {
71     freopen("crypt1.in", "r", stdin);
72     freopen("crypt1.out", "w", stdout);
73     scanf("%d", &N);
74     for (int i = 0; i < N; ++i) {
75         scanf("%d", &myArr[i]);
76     }
77     Solve();
78     return 0;
79 }

Combination Lock：
思路：
（1）根据 N 可以求出：
1）农夫约翰的号码组合所能产生的不同的开锁号码组合的数目 S1；
2）预设号码组合所能产生的不同的开锁号码组合的数目 S2。
（2）再求出以上1）和2）相同的号码个数 S3。
（3）推出答案： S1 + S2 - S3

注意：锁上标号为 N 的号码在程序中用 0 表示

 1 /*
 2 ID: Jming
 3 PROG: combo
 4 LANG: C++
 5 */
 6 
 7 #include <iostream>
 8 #include <cstdlib>
 9 #include <cstdio>
10 #include <cmath>
11 #include <algorithm>
12 #include <functional>
13 #include <string>
14 #include <cstring>
15 #include <vector>
16 #include <stack>
17 #include <queue>
18 #include <map>
19 using namespace std;
20 #define eps 1e-8
21 int N, Sum;
22 vector<int> arr0[3], arr1[3];
23 
24 int Ini(vector<int> arr[3]) {
25     int cnt = 1;
26     int tmp;
27     for (int i = 0; i < 3; ++i) {
28         scanf("%d", &tmp);
29         int pos = 0;
30         for (int j = -2; j <= 2; ++j) {
31             int mytmp = (tmp + j + N) % N;   
32             if (find(arr[i].begin(), arr[i].end(), mytmp) == arr[i].end()) {
33                 arr[i].push_back(mytmp);
34             }
35         }
36         cnt *= arr[i].size();
37     }
38     return cnt;
39 }
40 
41 void Solve() {
42     int mycount = 1;
43     for (int i = 0; i < 3; ++i) {
44         int tmp = 0;
45         for (int j = 0; j < arr0[i].size(); ++j) {
46             if (find(arr1[i].begin(), arr1[i].end(), arr0[i][j]) != arr1[i].end()) {
47                 ++tmp;
48             }
49         }
50         mycount *= tmp;
51     }
52     printf("%d
", Sum - mycount);
53 }
54 
55 int main()
56 {
57     freopen("combo.in", "r", stdin);
58     freopen("combo.out", "w", stdout);
59     scanf("%d", &N); 
60     Sum = 0;
61     Sum += Ini(arr0);
62     Sum += Ini(arr1);
63     Solve();
64     return 0;
65 }

Wormholes:

  1 /*
  2 此题参考了正解。
  3 关键：
  4   （1）枚举出所有两两匹配的情况。
  5     eg: 1 2 3 4 
  6       1）1-2 3-4
  7       2）1-3 2-4
  8       3）1-4 2-3
  9       所以共三种情况。
 10     解决办法：搜索（题目样例的搜索过程：参考示意图Wormholes.png）
 11   （2）判断匹配后的情况，是否会出现死循环。
 12 
 13 */
 14 /*
 15 ID: Jming
 16 PROG: wormhole
 17 LANG: C++
 18 */
 19 #include <iostream>
 20 #include <fstream>
 21 #include <cstdlib>
 22 #include <cstdio>
 23 #include <algorithm>
 24 #include <cstring>
 25 #include <vector>
 26 using namespace std;
 27 const int MAX_N = 15;
 28 int N;
 29 int Pair[MAX_N];
 30 int nextNd[MAX_N];
 31 
 32 typedef struct Node {
 33   int x;
 34   int y;
 35 } Node;
 36 
 37 vector<Node> wormhole;
 38 
 39 // 判断是否有死循环
 40 bool isCycle() {
 41   for (int i = 0; i < N; ++i) {
 42     // 枚举每一个点作为出发点
 43     int pos = i;
 44     for (int j = 0; j < N; ++j) {
 45       if (pos == -1 || Pair[pos] == -1) continue;
 46       pos = nextNd[Pair[pos]];
 47     }
 48     if (pos != -1) return true;
 49   }
 50   return false;
 51 }
 52 
 53 // 枚举所有情况
 54 int Solve() {
 55   int i = 0;
 56   int ans = 0;
 57   // 找到第一个尚未匹配的点
 58   for (; i < N; ++i) {
 59     if (Pair[i] == -1) break;
 60   }
 61   // 所有点都有了匹配的点？
 62   if (i == N) {
 63     if (isCycle()) return 1;
 64     else return 0;
 65   }
 66   // 枚举所有可能与 i 匹配的点 nd
 67   for (int nd = i + 1; nd < N; ++nd) {
 68     if (Pair[nd] == -1) {
 69       // 匹配点i 和 点nd，继续匹配
 70       Pair[i] = nd;
 71       Pair[nd] = i;
 72       ans += Solve();
 73       // 释放，枚举其他情况
 74       Pair[nd] = -1;
 75       Pair[i] = -1;
 76     }
 77   }
 78   return ans;
 79 }
 80 
 81 int main() {
 82   ifstream fin("wormhole.in");
 83   ofstream fout("wormhole.out");
 84   fin >> N;
 85   Node ndTmp;
 86   for (int i = 0; i < N; ++i) {
 87     fin >> ndTmp.x >> ndTmp.y;
 88     wormhole.push_back(ndTmp);
 89   }
 90   fin.close();
 91   int xxx = sizeof(nextNd);
 92   fill(nextNd, nextNd + MAX_N, -1);
 93   fill(Pair, Pair + MAX_N, -1);
 94   // 将(每个点)和(其右边最近的点)对应起来,保存于nextNd[]
 95   // 用于判断是否陷入死循环
 96   for (int i = 0; i < N; ++i) {
 97     for (int j = 0; j < N; ++j) {
 98       if (wormhole[i].y == wormhole[j].y && wormhole[i].x < wormhole[j].x) {
 99         if ((nextNd[i] == -1) ||
100           (wormhole[j].x - wormhole[i].x < wormhole[nextNd[i]].x - wormhole[i].x)) {
101           nextNd[i] = j;
102         }
103       }
104     }
105   }
106   fout << Solve() << endl;
107   fout.close();
108   return 0;
109 }

Wormholes.png

Ski Course Design:

 1 /*
 2 需要注意：
 3 change the height of a hill only once （一座山的高度只能改变一次）
 4 
 5 （根据答案进行了优化） 
 6 解法：枚举所有满足条件的高度区间
 7 (0, 17), (1, 18), (2, 19), ..., (83, 100)
 8 计算出使测试数据满足各个区间的花费，最小的即答案。
 9 时间复杂度：O(M*N) 100*1000 = 10^5
10 */
11 /*
12 ID: Jming
13 PROG: skidesign
14 LANG: C++
15 */
16 #include <iostream>
17 #include <fstream>
18 #include <cstdlib>
19 #include <cstdio>
20 #include <algorithm>
21 #include <cmath>
22 #include <cstring>
23 #include <vector>
24 using namespace std;
25 #define INF 0x3f3f3f3f
26 #define MAX_N 1005
27 
28 int hill[MAX_N];
29 int N;
30 
31 int Solve() {
32     int ans = INF;
33     for (int lowest = 0; lowest <= 83; ++lowest) {
34         int cost = 0, x;
35         for (int i = 0; i < N; ++i) {
36             if (hill[i] < lowest) {
37                 x = lowest - hill[i];
38             }
39             else {
40                 if (hill[i] > lowest + 17) {
41                     x = hill[i] - (lowest + 17);
42                 }
43                 else {
44                     x = 0;
45                 }
46             }
47             cost += x*x;
48         }
49         ans = min(ans, cost);
50     }
51     //cout << ans << endl;
52     return ans;
53 }
54 
55 int main() {
56     ifstream fin("skidesign.in");
57     ofstream fout("skidesign.out");
58 
59     fin >> N;
60     for (int i = 0; i < N; ++i) {
61         fin >> hill[i];
62     }
63     fout << Solve() << endl;
64 
65     fin.close();
66     fout.close();
67     return 0;
68 }