- 硬币问题
- 区间问题
- 字典序
- 其他
- Saruman’s Army
- Fence Repair
我们可以通过做出局部最优选择来构造全局最优解，我们直接做出当前问题中看来最优的选择，而不必考虑子问题的解。
贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题实例变得更小。
2.2.1 硬币问题
从￥500~￥1每次选择尽可能多的硬币个数。
<pre><code>
//
// Created by Nathan on 15/3/22.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// V: 2 0 3 1 2 3
// A: 620
//
include <iostream>
using namespace std;
int coin[6];
const int v[6]={1,5,10,50,100,500};
int A;
int solve(){
int res = 0;
int tmp = 0;
for (int i = 5;i>=0 ; i--) {
if(coin[i]&&(A-tmp)/v[i]){
int s = min((A-tmp)/v[i],coin[i]);
res += s;
tmp += s*v[i];
}
}
if(tmp==A) return res;
return 0;
}
int main(int argc, const char * argv[]) {
for (int i = 0; i<6; i++) {
cin >> coin[i];
}
cin >> A;
cout << solve() << endl;
return 0;
}
</code></pre>
2.2.2 区间问题
正确的算法：在可选的工作中，每次都选择最早结束的工作。
<pre><code>
//
// Created by Nathan on 15/3/22.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// 5
// 1 2 4 6 8
// 3 5 7 9 10
//
include <iostream>
using namespace std;
const int N =100000;
int n,s[N],t[N];
typedef pair<int, int>P;
pair<int,int>V[N];
int solve(){
for (int i = 0;i < n;i++) {
V[i].first = t[i];
V[i].second = s[i];
}
sort(V, V+n);
int res = 0,t=0;
for (int i = 0; i < n ;i++) {
if(t < V[i].second){
t = V[i].first;
res++;
}
}
return res;
}
int main( int argc, const char * argv[]) {
cin >> n;
for (int i = 0; i<n; i++) {
cin >> s[i];
}
for (int i = 0; i<n; i++) {
cin >> t[i];
}
int res = solve();
cout << res << endl;
return 0;
}
</code></pre>
2.2.3 字典序最小问题
什么是 字典序 ？
<pre><code>
//
// Created by Nathan on 15/3/22.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// N = 6
// S : ACDBCB
//
include <iostream>
using namespace std;
const int N = 2000;
char S[N];
int n;
void solve(){
int a = 0 , b = n-1;
while (a<=b) {
bool left = false;
if(S[a] < S[b]){
left = true;
}
if (left) {
cout << S[a++];
} else {
cout << S[b--];
}
}
}
int main(int argc, const char * argv[]) {
cin >> n;
for (int i = 0; i < 6; i++) {
cin >> S[i];
}
solve();
return 0;
}
</code></pre>
2.2.4 其他
1. Saruman’s Army
思路：每次选择范围以外的最近一点作为下次遍历的初始点。
<pre><code>
//
// Created by Nathan on 15/3/23.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// N = 6,R = 10
// X = 1,7,15,20,30,50
//
include <iostream>
using namespace std;
const int MAX_N = 1000;
int X[MAX_N],N,R;
int solve(){
sort(X, X+N);
int i=0 ,ans=0;
while (i < N) {
int s = X[i++];
while ( i < N && X[i] <= s+R) {
i++;
}
int p = X[i-1];
while (i < N && X[i] <= p+R) {
i++;
}
ans++;
}
return ans;
}
int main(int argc, const char * argv[]) {
cin >> N >> R;
for (int i = 0; i < N; i++) {
cin >> X[i];
}
int res = solve();
cout << res << endl;
return 0;
}
</code></pre>
2. Fence Repair
思路：寻找最小的两个点，并从数据中删除，将这两个点的和放入数组中，继续寻找最小的两个点，直至剩余一个点为止。
<pre><code>
//
// Created by Nathan on 15/3/23.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// N = 3
// L : 8,5,8
//
include <iostream>
using namespace std;
const int MAX_N = 20000;
int n,L[MAX_N];
void solve(){
long long ans = 0;
while ( n > 1) {
int mii1 = 0,mii2=1;
if (L[mii1] > L[mii2]) {
swap(L[mii1], L[mii2]);
}
for (int i = 2; i < n; i++) {
if (L[i] < L[mii1]) {
mii2 = mii1;
mii1 = i;
} else if(L[i] < L[mii2]){
mii2 = i;
}
}
int t = L[mii1]+L[mii2];
ans +=t;
if(mii1==n-1){
swap(mii1, mii2);
}
L[mii1] = t;
L[mii2] = L[n-1];
n--;
}
cout << ans << endl;
}
int main(int argc, const char * argv[]) {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> L[i];
}
solve();
return 0;
}
</code></pre>
