SGU186 解题手记
　　这个破题实在是看不明白。
----------From SGU Forum------------
Author: Rafail
ID: 003796
Problem: 186
Contest: 0
Date: 2003-12-17 22:38:36

Ivan...
Is seems to me, you misunderstood the specification. At first, I was sure it was totally incomprehensible, too. But my solution was accepted at last... So I hope the God lets the following explanation be helpful to you (or anybody else trying to solve this problem):

If you have 2 links 1 1, let us represent them as follows: O O.
It will take you 1 minute (according to the problem specification) to:
1. to unchain the left link : U O
2. to put into the unchained link the second link : UO
3. to chain the unchained link : OO

If you have 3 links 1 1 1 (O O O), it may take you 2 minutes to reach the aim:
MINUTE #1
1. you unchain link #1 : U O O
2. you put link #2 into it : UO O
3. you chain link #1 back : OO O
Now you have 2 links 2 1 (OO O). What are we going to do next?
MINUTE #2
1. you unchain link #2 : OU O
2. you put link #3 into it : OUO
3. you chain link #2 back : OOO

You can also save some time and do everything in a minute as follows:
1. you unchain link #2 : O U O
2. you put links #1 and #3 into it : OUO
3. you chain link #2 back : OOO

Good luck!
Best wishes,
Raphail
------------------------------------
　　给我的感觉是这样的，先从一个chain上拆一个link下来，然后用这个link把两条chain连接起来，这样耗时1分钟。为了最后耗时最短，就拆短的chain而连接长的chain。
　　Submit 1: AC。
　　我觉得这个题目的数据有问题，因为有一个明显写错的代码也AC了。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <cstdio>
#include <algorithm>
using namespace std;
 
int main()
{
    int chains[100];
    int n,time(0);
    scanf("%d",&n);
    for (int i=0;i<n;++i) scanf("%d",chains+i);
    sort(chains,chains+n);
    for (int rest=n-1,i=0;rest>0;rest-=chains[i]+1,i++)
        time+=min(rest,chains[i]);
    printf("%d\n",time);
    return 0;
}