A The Empire Age

1月28日

Description

帝国时代3是一款十分刺激的RTS游戏。你需要控制自己的一块殖民地，发展殖民地的经济和军事，最终打败其他殖民地。小L是这个游戏的狂热爱好者。一次小L打算打AI试试身手。

小L发展了几分钟，自己的殖民地人口便突破了30，然而小L发现大事不好了：

小L还处在不能建造军事单位的“发现时代”，然而敌人早已经到了“殖民时代”，发展起了一支雄厚的殖民地军，小L的殖民地受攻击了却没有一个正规的军事单位用来防御！不要认为这是小L 的技术问题，实际上AI还停留在以jg斗争为纲的落后理念上，而小L 早就以经济为第一要务了。

小L在之前已经在自己殖民地的外部，拉起了许多围墙。

帝国时代3里的围墙如图所示。

图的地址太长了不引用了

每一道围墙，总是连接着两个围墙连接处 (以下简称“连接处”)。

图的地址太长了不引用了

现在小L有n个连接处，m道围墙。

小L虽然没兵，但是他的智商比AI不知道高到那里去了，因此，只要每个连接处至少连接着k道围墙，小L就一定能顶住这波攻击。

小L可以任意加围墙，每道围墙可以连接两个已有的连接处。

连接处是不能连接自己的，但是这里有一些规则与原帝国时代3的设定不同，两个连接处之间可以连接多个围墙，连接处初始时可能不连任何围墙，围墙之间也可以相交。

小L想知道，自己至少要多加多少道围墙}才能满足每个连接处至少连接着k道围墙？

Input

第一行三个整数n, m, k，表示连接处个数、围墙个数以及每个连接处至少要连接的围墙个数，连接处被编号为1到n}。

接下来m行，每行两个正整数x, y，表示这个围墙连接编号为x的连接处和编号为y的连接处。

Output

输出一行一个整数，表示至少要加的围墙的条数。

Sample Input

输入1：

2 0 1

输入2：

输入3：

输入4：

Sample Output

输出1：

样例1解释：初始时有两个连接处，题目中要求至少每个连接处要连1个围墙，我们加一个围墙连接这两个连接处即可。

输出2：

样例2解释：连接编号为5的和编号为4的连接处即可。

输出3：

样例3解释：编号为4的连接处没有连接任何围墙，编号为3的连接处还需要一条。连接编号为4的和编号为3的连接处之后，编号为4的连接处与另外三个连接处中任意一个连一个围墙即可，注意连接处是不能自己和自己连接的。

输出4：

Data Constraint

对于60%的数据，n × ans ≤ 10000000，ans表示最终的答案。

对于前100%的数据，n, m, k ≤ 100000，n ≥ 2, m, k ≥ 0, x ≠ y, 1 ≤ x, y ≤ n。

Solution

【我的解法】

看完了题后愣了几秒，然后打了个小根堆。。。本来是只有60分的，但是出题人过于友善，只卡了我一个点，拿了90分。

#include<cstdio>

#include<queue>

#pragma GCC optimize(2)

#define ll long long

using namespace std;

int n,m,k;

ll cnt;

ll a[100001];

priority_queue<ll,vector<ll>,greater<ll> > que;

inline int read()

{

	int x=0; char c=getchar();

	while (c<'0' || c>'9') c=getchar();

	while (c>='0' && c<='9')

	{

		x=(x<<1)+(x<<3)+(c^48);

		c=getchar();

	}

	return x;

}

int main()

{

	freopen("A.in","r",stdin);

	n=read();m=read();k=read();

	for(int i=1,x,y;i<=m;i++)

	{

		x=read();y=read();

		a[x]++;a[y]++;

	}

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

		que.push(a[i]);

	while(!que.empty())

	{

		a[1]=que.top();que.pop();

		if(a[1]>=k) break;

		a[2]=que.top();que.pop();

		a[1]++;a[2]++;

		cnt++;

		que.push(a[1]);

		que.push(a[2]);

	}

	printf("%lld",cnt);

	fclose(stdin);

	return 0;

}

【正解】

直接统计出每个点还需要多少个度数，如果需要度数最多的点大于其他度数的总和，那么答案就是这个点的度数。否则就是所有点需要的度数的总和除以二向上取整。

复杂度就是读入复杂度。

#include<cstdio>

#include<cmath>

#include<algorithm>

#pragma GCC optimize(2)

#define ll long long

using namespace std;

int n,m,k;

ll cnt,maxn;

ll a[100001];

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1,x,y;i<=m;i++)

	{

		scanf("%d%d",&x,&y);

		a[x]++;a[y]++;

	}

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

	{

		if(k<a[i]) continue;

		a[i]=k-a[i];

		maxn=max(maxn,a[i]);

		cnt+=a[i];

	}

	if(ceil(cnt/2.0)<maxn)

	{

		printf("%lld",maxn);

		return 0;

	}

	printf("%lld",(cnt+1)/2);

	return 0;

}

巴特西