UESTC--1263--The Desire of Asuna（贪心）

Time Limit: 1000MS

Memory Limit: 65535KB

64bit IO Format: %lld & %llu

Description

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

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

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

Input

第一行是一个整数 $n$ ( $1\le n \le 2000$), 表示有 $n$ 条荧光链。

接下来一行有 $n$ 个数，每个数 $a_i$ ($1 \le a_i \le 10^5$)表示第 $i$ 条链由 $a_i$ 个荧光圈相互连接

Output

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

Sample Input

3

3 2 1

3

4 3 4

Sample Output

Hint

第一组样例解释：

Source

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

有点坑，刚开始没理解题意

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 1010

#define MAXM 10010

#define INF 0x3f3f3f

int num[MAXM];

int main()

{

	int n;

	while(scanf("%d",&n)!=EOF)

	{

		for(int i=0;i<n;i++)

		scanf("%d",&num[i]);

		sort(num,num+n);

		int ans=0;

		for(int i=0;n>1;i++)

		{

			if(num[i]+1<n)

			{

				ans+=num[i];

				n-=(num[i]+1);

			}

			else

			{

				ans+=n-1;

				break;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

UESTC--1263--The Desire of Asuna（贪心）

最新文章

热门文章