UESTC 1263-The Desire of Asuna

叁歲伎倆 2022-08-19 13:19 41阅读 0赞

# The Desire of Asuna #

[Edit][]

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

ZYHAzwraith用自己心爱的键盘换来了很多支漂亮的荧光棒！

一天，他准备用一条由很多个莹光圈相互连接而成的荧光链送给女神Asuna。每个荧光圈只能由一支荧光棒首尾相接成一个环得到。现在他手中有 n 条荧光链，为了最后把这些链拼接成一条链，每次他可以选择任意一条荧光链中的任意一个荧光圈并用魔法把这个圈断开，然后用这个断开的荧光圈去连接任意两条荧光链使之成为一条。

现在ZYHAzwraith想知道最少需要多少次才能把这些荧光链链拼接成一条长链？

## Input ##

第一行是一个整数 n ( 1≤n≤2000 ), 表示有 n 条荧光链。 接下来一行有 n 个数，每个数 a i (1≤a i ≤10 5 )表示第 i 条链由 a i 个荧光圈相互连接

## Output ##

输出一个整数表示最少的次数。

## Sample input and output ##

<table> 
 <thead> 
  <tr> 
   <th>Sample Input</th> 
   <th>Sample Output</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td> <pre><code>3
3 2 1</code></pre> </td> 
   <td> <pre><code>1</code></pre> </td> 
  </tr> 
  <tr> 
   <td> <pre><code>3
4 3 4  </code></pre> </td> 
   <td> <pre><code>2</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

## Hint ##

第一组样例解释： ![Center][]

## Source ##

第七届ACM趣味程序设计竞赛第三场（正式赛）

解题思路：

将环从小到大排序，排序完再减去每个串上的环的同时，注意当本串全都用于连接时总的条数将减一。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int map[1010000];
    bool cmp(int x,int y)
    {
    	return x<y;
    }
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		int ans=0;
    		int i,j;
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&map[i]);
    		}
    		i=0;
    		sort(map,map+n,cmp);
    		while(ans!=n-1)
    		{
    			if(map[i]!=0)
    			{
    				map[i]--;
    				ans++;
    			}
    			else
    			{
    				i++;
    				n--;
    			}
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[Edit]: http://acm.uestc.edu.cn/#/problem/editor/1263
[Center]: /images/20220731/f9f8e4edcd0a4e95a99daf7abcdad205.png