贪心算法例题

• 硬币问题

   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 }