codeforces 659C . Tanya and Toys 二分

题目链接

将给出的已经有了的排序，在前面加上0，后面加上1e9+1。

然后对相邻的两项判断。如果相邻两项之间的数的和小于m，那么全都选上， m减去相应的值。

如果大于m，那么二分判断最多能选多少个。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <complex>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

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

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef complex <double> cmx;

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9+7;

const int inf = 1061109567;

const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

const int maxn = 1e5+5;

int ans[maxn], a[maxn], cnt;

int check(int l, int r, int sum) {

    int len = r-l+1;

    ll tmp = 1LL*(l+r)*len/2;

    if(tmp<=sum)

        return 1;

    return 0;

}

void bin(int l, int r, int sum) {

    int pos = l;

    int tmpl = l;

    while(l<=r) {

        int m = l+r>>1;

        if(check(tmpl, m, sum)) {

            pos = m;

            l = m+1;

        } else

            r = m-1;

    }

    for(int i = tmpl; i <= pos; i++)

        ans[cnt++] = i;

}

int main()

{

    int n, m;

    cin>>n>>m;

    a[0] = 0;

    for(int i = 1; i <= n; i++)

        scanf("%d", &a[i]);

    a[++n] = 1e9+1;

    sort(a, a+n+1);

    for(int i = 0; i < n; i++) {

        int tmp = a[i+1]-a[i];

        if(tmp==1)

            continue;

        if(tmp==2) {

            if(m>=a[i]+1) {

                m -= (a[i]+1);

                ans[cnt++] = a[i]+1;

                continue;

            } else

                break;

        }

        int a1 = a[i]+1, an = a[i+1]-1;

        tmp--;

        ll sum = 1LL*(a1+an)*tmp/2;

        if(sum<=m) {

            m -= sum;

            for(int j = a[i]+1; j<=a[i+1]-1; j++) {

                ans[cnt++] = j;

            }

        } else {

            if(a1<=m) {

                bin(a1, an, m);

            }

            break;

        }

    }

    cout<<cnt<<endl;

    for(int i = 0; i < cnt; i++)

        printf("%d ", ans[i]);

    return 0;

}

巴特西

codeforces 659C . Tanya and Toys 二分

题目链接

最新文章

热门文章