2018.09.08 NOIP模拟eat（贪心）

签到水题啊。。。

这题完全跟图论没有关系。

显然如果确定了哪些点会被选之后顺序已经不重要了。于是我们给点按权值排序贪心从大向小选。

我们要求的显然就是∑i(a[i]−(n−i))” role=”presentation” style=”position: relative;”>∑i(a[i]−(n−i))∑i(a[i]−(n−i))

当这个贡献非正时停止枚举。

然后就没了。

代码：

#include<bits/stdc++.h>#define ll long long#define N 200005using namespace std;inline ll read(){    ll ans=0;    char ch=getchar();    while(!isdigit(ch))ch=getchar();    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return ans;}int n,m;ll a[N],ans=0;int main(){    freopen("eat.in","r",stdin);    freopen("eat.out","w",stdout);    n=read(),m=read();    for(int i=1;i<=n;++i)a[i]=read();    for(int i=1;i<=m;++i)int x=read(),y=read();    sort(a+1,a+n+1);    for(int i=n,cnt=0;i;--i,++cnt){        if(a[i]<=cnt)break;        ans+=a[i]-cnt;    }    cout<<ans;    return 0;}