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:
5 4 2
1 2
2 5
4 3
3 1
输入3:
4 3 2
1 2
2 3
1 2
输入4:
5 11 7
1 3
4 2
1 5
4 2
2 5
1 3
4 1
2 3
4 1
5 1
1 5
Sample Output
输出1:
1
样例1解释:初始时有两个连接处,题目中要求至少每个连接处要连1个围墙,我们加一个围墙连接这两个连接处即可。
输出2:
1
样例2解释:连接编号为5的和编号为4的连接处即可。
输出3:
2
样例3解释:编号为4的连接处没有连接任何围墙,编号为3的连接处还需要一条。连接编号为4的和编号为3的连接处之后,编号为4的连接处与另外三个连接处中任意一个连一个围墙即可,注意连接处是不能自己和自己连接的。
输出4:
7
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;
}