USACO 之 Section 1.3 Greedy Algorithm （已解决）-白红宇

USACO 之 Section 1.3 Greedy Algorithm （已解决）

阅读量：4616 次

发布时间：2019-06-09

本文共 8993 字，大约阅读时间需要 29 分钟。

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

1 /* 2 ID: Jming 3 PROG: milk 4 LANG: C++ 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         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\n", 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 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 #include 
           
            13 #include 
            
             14 #include 
             
              15 #include 
              
               16 #include 
               
                17 #include 
                
                 18 #include 
                 19 using namespace std;20 #define eps 1e-821 #define MAX_C 20522 23 int M, S, C;24 int myArr[MAX_C];25 vector
                  
                    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\n", 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\n", C);64 return 0;65 }66 if (1 == M) {67 printf("%d\n", 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 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           13 #include 
           
            14 #include 
            
             15 #include 
             
              16 #include 
              
               17 #include 
               
                18 #include 
                19 using namespace std;20 #define eps 1e-821 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\n", 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 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           13 #include 
           
            14 #include 
            
             15 #include 
             
              16 #include 
              
               17 #include 
               
                18 #include 
                19 using namespace std;20 #define eps 1e-821 int N, Sum;22 vector
                 
                   arr0[3], arr1[3];23 24 int Ini(vector
                  
                    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\n", 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 
     
       20 #include 
      
        21 #include 
       
         22 #include 
        
          23 #include 
         
           24 #include 
          
            25 #include 
           
             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
            
              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^510 */11 /*12 ID: Jming13 PROG: skidesign14 LANG: C++15 */16 #include 
     
      17 #include 
      
       18 #include 
       
        19 #include 
        
         20 #include 
         
          21 #include 
          
           22 #include 
           
            23 #include 
            
             24 using namespace std;25 #define INF 0x3f3f3f3f26 #define MAX_N 100527 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 }

转载于:https://www.cnblogs.com/shijianming/p/4140798.html

你可能感兴趣的文章