186. The Chain
time limit per test: 0.25 sec.memory limit per test: 4096 KB
input: standard inputoutput: standard output
Smith has N chains. Each chain is the sequence of successively connected links. The length of each chain is known: the first chain contains L1 links, the second – L2, …, the last one – LN.He can make a following series of actions in a minute:1. to unchain one link2. to remove or to put into the unchained link some other links of any chain3. to chain the linkYour task is to determine the minimum time which will take the smith to connect all the chains in one line, i.e. the chain will look like a chain made up of successively connected links.
Input
The first line contains natural number N<=100. The second line contains L1, L2, …, LN (1<=Li<=100, for all i = 1..N).
Output
Output the only integer number – the solution to the problem.
Sample test(s)
Input
23 4
Output
1
[submit]
[forum]
Author:Michael R. Mirzayanov
Resource:ACM International Collegiate Programming Contest 2003-2004North-Eastern European Region, Southern Subregion
Date:2003 October, 9
思路:好无耻的英语,说的这么拐弯抹角真的好吗?题意应该是这样的,,先从一个chain上拆下一个link,然后可以连接两个chain,只到所有chain都连起来为止,这里算一分钟,所以先从短链开始拆更省时,贪心….
AC代码:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[105];int main() {int n;while(scanf("%d", &n) != EOF) {for(int i = 0; i < n; i++) {scanf("%d", &a[i]);}sort(a, a+n);int i = 0, j = n-1, ans = 0;while(i < j) {a[i]–;j–;if(a[i] == 0) i++;ans++;}printf("%d\n", ans);}return 0;}
有时我们选择改变,并非经过深思熟虑,而更像是听见了天地间冥冥中的呼唤,