硬币问题
- 题目大意:1元、5元、10元、50元、100元、500元硬币各C1、C5、C10、C50、C100、C500枚，用它们来支付A元，最少需要多少枚硬币，假定至少存在一种支付方案
- 限制条件：
- 0≤Ci≤109 i=1,5,10,50,100,500
- 0≤A≤109
- 思路：贪心算法中最简单的例子，优先使用面值大的硬币。贪心算法遵循某种规则，不断地选取当前最优策略。贪心算法通常是非常高效的。
区间调度问题
- 题目大意：有n项工作，每项工作分别在si时间开始，在ti时间结束，对于每项工作，你都可以选择参加与否，如果选择了参加，那么自始至终都必须全程参与，此外，参与工作的时间段不能重叠(即使是开始的瞬间和结束的瞬间的重叠也是不允许的)，求最多能参与多少项工作？
- 限制条件：
- 1≤N≤100000
- 1≤si≤ti≤109
- 思路：这个问题也可以通过贪心来求解，但不像硬币问题那样简单。我们可以设计出各种各样的贪心算法：
- 在可选的工作(也就是和目前已选的工作都不重叠的工作)中，每次都选取开始时间最早的工作
- 在可选的工作中，每次都选取结束时间最早的工作
- 在可选的工作中，每次都选取用时最短的工作
- 在可选的工作中，每次都选取与最少可选工作有重叠的工作
- 然而，这里面只有算法2是正确的，其余的算法都可以很找到很简单的反例，下面给出算法2正确性的证明：
- 设f[i]是算法2产生的第i个区间的右端点坐标，g[i]是最优解中第i个区间的右端点坐标，则由归纳法可知当i≥1时，必有f[i]≤g[i]；设最优解选出的区间数量为m，算法2选出的区间数量为k，由最优解的最优性，必有m≥k，假设m>k,由f[k]≤g[k]，知最优解选的的第k+1个区间一定位于f[k]之后，故算法2在选了第k个区间之后不会停止，还有区间可以选择，故算法2选出的区间数量大于k，产生矛盾，从而m=k，从而证明了算法2的正确性
字典序最小问题(POJ 3617)
- 原题如下：
Best Cow Line
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 32285 Accepted: 8560 Description
FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.
The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.
FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.
FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.
Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original lineOutput
The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.
Sample Input
6 A C D B C B
Sample Output
ABCBCD
- 思路：看完题目，很自然的可以想到贪心算法：不断取S的开头和结尾中较小的一个字符放到T的末尾，但对于相同的情形，我们还应该给出明确的选取方法，由于我们要尽快的将更小的字符加到新串T中，所以就要比较下一个字符，而下一个字符也可能相同，所以考虑将S反转之后和原串S进行比较，若S较小则将S开头的一个字符取出，加到新串T的结尾，否则将S结尾的一个字符取出，加到新串T的结尾
- 代码：
字典序最小问题11 #include <iostream> 2 3 using namespace std; 4 5 int n; 6 char *s; 7 int t=0; 8 9 int main() 10 { 11 cin >> n; 12 s = new char[n+1]; 13 for (int i=0; i<n; i++) cin >> s[i]; 14 if (n==1) cout << s[0]; 15 else 16 { 17 int l=0, r=n-1; 18 while (l<=r) 19 { 20 int i=l, j=r; 21 while (i<=j && s[i]==s[j]) 22 { 23 i++; 24 j--; 25 } 26 if (s[i]<s[j]) 27 { 28 t++; 29 cout << s[l++]; 30 if (t%80==0) cout << endl; 31 } 32 else 33 { 34 t++; 35 cout << s[r--]; 36 if (t%80==0) cout << endl; 37 } 38 } 39 } 40 }
-
再贴一段书上的代码：
字典序最小问题21 #include <cstdio> 2 3 using namespace std; 4 5 int n; 6 char *s; 7 int t; 8 9 int main() 10 { 11 scanf("%d",&n); 12 getchar(); 13 s = new char[n+1]; 14 for (int i=0; i<n; i++) 15 { 16 s[i]=getchar(); 17 getchar(); 18 } 19 int l=0, r=n-1; 20 while (l<=r) 21 { 22 bool left=false; 23 for (int i=0; l+i<=r; i++) 24 { 25 if (s[l+i]<s[r-i]) 26 { 27 left = true; 28 break; 29 } 30 else if (s[l+i]>s[r-i]) break; 31 } 32 if (left) 33 { 34 ++t; 35 putchar(s[l++]); 36 if (t%80==0) printf(" "); 37 } 38 else 39 { 40 ++t; 41 putchar(s[r--]); 42 if (t%80==0) printf(" "); 43 } 44 } 45 }
Saruman's Army(POJ 3069)
- 原题如下：
Saruman's Army
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14028 Accepted: 7038 Description
Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R units, and must be carried by some troop in the army (i.e., palantirs are not allowed to “free float” in mid-air). Help Saruman take control of Middle Earth by determining the minimum number of palantirs needed for Saruman to ensure that each of his minions is within R units of some palantir.
Input
The input test file will contain multiple cases. Each test case begins with a single line containing an integer R, the maximum effective range of all palantirs (where 0 ≤ R ≤ 1000), and an integer n, the number of troops in Saruman’s army (where 1 ≤ n ≤ 1000). The next line contains n integers, indicating the positions x1, …, xn of each troop (where 0 ≤ xi ≤ 1000). The end-of-file is marked by a test case with R = n = −1.
Output
For each test case, print a single integer indicating the minimum number of palantirs needed.
Sample Input
0 3 10 20 20 10 7 70 30 1 7 15 20 50 -1 -1
Sample Output
2 4
Hint
In the first test case, Saruman may place a palantir at positions 10 and 20. Here, note that a single palantir with range 0 can cover both of the troops at position 20.
In the second test case, Saruman can place palantirs at position 7 (covering troops at 1, 7, and 15), position 20 (covering positions 20 and 30), position 50, and position 70. Here, note that palantirs must be distributed among troops and are not allowed to “free float.” Thus, Saruman cannot place a palantir at position 60 to cover the troops at positions 50 and 70.
- 题解：我们可以从最左边的点开始考虑，对于这个点，其距离为R以内的区域里必须要有带有标记的点，带有标记的点一定在此点的右边，但究竟选它右边哪个点加上标记呢？这里我们的贪心策略是：从最左边的点开始，选择其距离为R以内的的区域里最远的点。因为更左的区域并没有覆盖的意义，所以应该覆盖更加靠右的点。加上第一个标记后，余下部分也用同样的办法处理，对于添加了标记的点的右侧相距超过R的下一个点，采用同样的办法找到其右侧相距R距离以内的最远的点添加标记即可，重复这一过程。
- 代码：
Saruman's Army
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 6 bool compare(int a, int b) 7 { 8 return a<b; 9 } 10 11 int n,r; 12 int * x; 13 14 int main() 15 { 16 cin >> r >> n; 17 while (r!=-1 && n!=-1) 18 { 19 int ans=0; 20 x = new int[n]; 21 for (int i=0; i<n; i++) cin >> x[i]; 22 sort(x,x+n,compare); 23 int i=0; 24 while (i<n) 25 { 26 int s=x[i++]; 27 while(i<n && x[i]-s<=r) i++; 28 int p=x[i-1]; 29 ans++; 30 while(i<n && x[i]-p<=r) i++; 31 } 32 cout << ans << endl; 33 delete[] x; 34 cin >> r >> n; 35 } 36 }
Fence Repair(POJ 3253)
- 原题如下：
Fence Repair
Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 60998 Accepted: 20117 Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.
Input
Line 1: One integer N, the number of planks
Lines 2..N+1: Each line contains a single integer describing the length of a needed plankOutput
Line 1: One integer: the minimum amount of money he must spend to make N-1 cutsSample Input
3 8 5 8
Sample Output
34
Hint
He wants to cut a board of length 21 into pieces of lengths 8, 5, and 8.
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34). - 题解：首先，切割的方法可以用二叉树来描述，例如：
15 / 7 8 / / 3 4 5 3 / 1 2
这里每一个叶子节点就对应了切割出的一块块木板，叶子节点的深度就对应了为了得到对应木板所需的切割次数，开销的合计就是各叶子节点的"木板的长度*节点的深度"的总和。(这题其实就是裸的哈夫曼树→_→)于是，此时的最佳切割方法首先应该具有这样的性质：最短的板和次短的板的节点应当是兄弟节点。对于最优解来讲，最短的板应当是深度最大的叶子节点之一，所以与这个叶子节点同一深度的兄弟节点一定存在，并且由于同样是最深的叶子节点，所以应该对应于次短的板。不妨将Li从小到大排序，最短的是L1，次短的是L2，它们在二叉树里是兄弟节点，它们是从一块长度为（L1+L2）的板切割来的，由于切割顺序是自由的，不妨当作是最后一次切割，则这次切割前有(L1+L2)、L3、L4、…、Ln,这样的n-1块木板存在，按照相同的方式，将这n-1块木板进行处理，就可以得到整个问题的答案了，复杂度是O(N2)的，使用堆优化后可以达到O(nlogn)的复杂度。
- 代码：
Fence Repair
1 #include <iostream> 2 using namespace std; 3 4 int n; 5 int *l; 6 7 int main() 8 { 9 cin >> n; 10 l = new int[n]; 11 for (int i=0; i<n; i++) 12 { 13 cin >> l[i]; 14 } 15 long long ans=0; 16 while (n>1) 17 { 18 int min1=0,min2=1; 19 if (l[min1]>l[min2]) 20 { 21 min1=1; 22 min2=0; 23 } 24 for (int i=2; i<n; i++) 25 { 26 if (i[l]<min1[l]) 27 { 28 min2=min1; 29 min1=i; 30 } 31 else if(i[l]<min2[l]) min2=i; 32 } 33 int t=min1[l]+min2[l]; 34 ans += t; 35 if (min1==n-1) 36 { 37 min1=min2; 38 min2=n-1; 39 } 40 min1[l]=t; 41 l[min2]=l[n-1]; 42 n--; 43 } 44 cout << ans << endl; 45 }