题目大意:

要求构建一个长为n的数组,其中每两种不同的元素必须有一对是相邻的

然后给出m个交易,如果数组中有q[i]这个元素,就给w[i]元钱,求最多能得到多少钱?

具体思路:

先求出有x个不同元素的最小长度,然后给钱排个序就好啦

怎么求最小长度呢?可以把数组看成一个完全图的一条路径

最小长度大概就是一个欧拉路径啦,奇偶分类讨论一下就好啦

 

AC代码

#include
     
      #define int long longusing namespace std;int a[5000000],b[5000000],x,y,i,j,n,m;main(){    scanf("%I64d%I64d",&n,&m);    for(i=2;i<=100000;i++)if((i-1)%2==0)a[i]=i*(i-1)/2+1;else a[i]=i*(i-1)/2+1+(i-2)/2;    for(i=1;i<=m;i++)scanf("%I64d%I64d",&x,&y),b[x]+=y;    sort(b+1,b+1+1000000);    int top=0;    while(n>=a[top])top++;    top--;    int ans=0;    for(i=1;i<=top;i++)ans+=b[1000000-i+1];    printf("%I64d",ans);    return 0;}