【题目链接】:http://codeforces.com/problemset/problem/367/C

【题意】



我们称一个数列a[N]美丽;

当且仅当,数列中出现的每一对数字都有相邻的.

给你n的大小;

以及m个数字以及它们的使用花费;

问你最多能花费多少钱;

使得选择的这些数字能够构成一个长度为n的美丽数列;

【题解】



显然选什么数字,只要是不一样的就可以了;和数字具体是什么无关;

要算出的就是最多能选几个数字N;

这里,数字的相邻关系能构成一张图;

完全图->每个点都与其他n-1个点有边;

->N*(N-1)/2条边;

然后如果我们每一条边都走一遍,然后把点按照经过的顺序输出的话不就能满足要求了吗?

->欧拉路;

这里如果N为奇数的话;

刚好,每个点的度数都为偶数;可以构成欧拉路;

边数为n*(n-1)/2

如果N为偶数的话;

每个点的度数都为奇数;

我们可以不用全都变成偶数;

因为只有两个奇点的话也能构成欧拉路;

->连(N-2)/2条边就能做到;

所需边数为n*(n-1)/2 + (n-2)/2

然后因为有n个位置;

所以最多能用n-1条边;

直接枚举点数获得N就好;

然后取最贵的N条边(排个序)



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e5+100;

int n,m;

pii a[N];

int main(){

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n >> m;

    rep1(i,1,m){

        cin >> a[i].fi >> a[i].se;

    }

    sort(a+1,a+1+m,[&] (pii a,pii b) { return a.se > b.se;});

    LL cur = 1;

    while (cur <= m){

        if (cur%2==1){

            LL temp = cur*(cur-1)/2;

            if (temp >n - 1) break;

        }else{

            LL temp = cur*(cur-1)/2;

            temp += (cur-2)/2;

            if (temp > n - 1) break;

        }

        cur++;

    }

    LL ans = 0;

    rep1(i,1,cur-1){

        ans+=a[i].se;

    }

    cout << ans << endl;

    return 0;

}