【2018/09/08】T1-签到题-eat（WOJ 3931）

传送门

 分析

我简直醉了，这道题居然那么简单！！！！（所谓签到题，就是说只要去了就可以AC）

这道题和图论完全没有关系，题目中说明了所有点都和1联通，那么任意一个点都可以走到，且答案与走的顺序没有关系。为什么呢？因为如果第一天吃了 a[n] 的人，那么第二天就只能吃 a[n-1]-1 个人：

 a[n]-0 + a[n-1]-1 + a[n-2]-2 + ...... + a[k]-k+ a[k-1]-(k-1)+......

然后到达某一天的时候a[k]-k就是负数了，那么肯定没有 不加这个城市的时候优秀，就不管啦

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 200009
#define in read()
#define ll long long
using namespace std;
int n,m,a[N];
ll ans=0;
inline int read(){
char ch;int f=1,res=0;
while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return f==1?res:-res;
}
int main(){
scanf("%d%d",&n,&m);
int i,j,k,t=0;
for(i=1;i<=n;++i)	a[i]=in;
sort(a+1,a+n+1);
for(i=n;i>=1;--i){
if(a[i]<=t) break;
ans+=a[i]-t;t++;
}
printf("%lld",ans);
return 0;
}

最后

以上就是跳跃灰狼为你收集整理的【2018/09/08】T1-签到题-eat（WOJ 3931）的全部内容，希望文章能够帮你解决【2018/09/08】T1-签到题-eat（WOJ 3931）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。