貪心算法例題

• 硬币問題

  

  

  1 // 硬币的面值
   2 const int V[6] = {1, 5, 10, 50, 100, 500};
   3 
   4 // 輸入
   5 int C[6]; // C[0] = C_1, C[1] = C_5, ...
   6 int A;
   7 
   8 void solve() {
   9     int ans = 0;
  10     for (int i = 5; i >= 0; i--) {
  11         int t = min(A / V[i], C[i]); //使用硬币i的枚數
  12         A -= t * V[i];
  13         ans += t;
  14     }
  15 
  16     printf("%d\n", ans);
  17 }      

• 區間問題

  

  

  

  1 const int MAX_N = 100000;
   2 
   3 // 輸入
   4 int N, S[MAX_N], T[MAX_N];
   5 
   6 // 用于對工作排序的pair數組
   7 pair<int, int> itv[MAX_N];
   8 
   9 void solve() {
  10     // 對pair進行的是字典序比較
  11     // 為了讓結束時間早的工作排在前面，把T存入first，把S存入second
  12     for (int i = 0; i < N; i++) {
  13         itv[i].first = T[i];
  14         itv[i].second = S[i];
  15     }
  16     sort(itv, itv + N);
  17 
  18     // t是最後所選工作的結束時間
  19     int ans = 0, t = 0;
  20     for (int i = 0; i < N; i++) {
  21         if (t < itv[i].second) {
  22             ans++;
  23             t = itv[i].first;
  24         }
  25     }
  26 
  27     printf("%d\n", ans);
  28 }      

• 字典序最小問題

  

• 

  1 // 輸入
   2 int N;
   3 char S[MAX_N + 1];
   4 
   5 void solve() {
   6     // 剩餘的字元串為S[a], S[a+1], ..., S[b]
   7     int a = 0, b = N - 1;
   8 
   9     while (a <= b) {
  10         // 将從左起和從右起的字元串比較
  11         bool left = false;
  12         for (int i = 0; a + i <= b; i++) {
  13             if (S[a + i] < S[b - i]) {
  14                 left = true;
  15                 break;
  16             }
  17             else if (S[a + i] > S[b - i]) {
  18                 left = false;
  19                 break;
  20             }
  21         }
  22 
  23         if (left) putchar(S[a++]);
  24         else putchar(S[b--]);
  25     }
  26 
  27     putchar('\n');
  28 }