贪心算法

贪心算法就是遵循某种规则,不断贪心地选取当前最优策略的算法设计方法.

硬币问题

贪心策略: 贪最大币值就行

区间问题

贪心策略: 贪结束时间最早的工作

字典序最小问题

贪心策略:贪左右字典序最小的那个字母(相同则比较下一个)

#include<iostream>
#define MAX_N 2000
using namespace std;
int N;
char s[MAX_N+1];
int main() {
  cin >> N;
  int i=0;
  while(i < N) {
    cin >> s[i];
    i++;
  }
  int a = 0, b=N-1;
  while (a <= b)
  {
    bool left = false;
    for (int i=0; a+i <=b; i++) {
      if (s[a+i] < s[b-i]) {
        left = true;
        break;
      } else if (s[a+i] > s[b-i]) {
        left = false;
        break;
      }
    }
    if(left) cout << s[a++];
    else cout << s[b--];
    if (N>80 && (a+N-b-1) % 80 == 0) cout << endl;
  }
  cout << endl;
  return 0;
}

其他例题

Saruman’s Army

http://poj.org/problem?id=3069
从左边开始一直贪最大的R

#include<iostream>
#include<algorithm>
#define MAX_N 1000
using namespace std;
int N, R;
int X[MAX_N+1];
void solve() {
  cin >> R >> N;
  while (N !=-1 && R !=-1) {
    for(int i=0; i<N; i++) cin >> X[i];
    sort(X, X+N);
    int i=0, res = 0;
    while (i<N) {
      //  s是没有覆盖的最左边的点
      int s = X[i++];
      while(i<N && X[i] <= s+R) i++;
      // p是新加上标记的点
      int p = X[i-1];
      while (i<N && X[i] <= p+R) i++;
      res++;
    }
    cout << res << endl;
    cin >> R >> N;
  }
}
int main() {
  solve();
  return 0;
}