codeforces 807 E. Prairie Partition（贪心+思维）

题目链接：http://codeforces.com/contest/807/problem/E

题意：已知每个数都能用x=1 + 2 + 4 + ... + 2k - 1 + r （k ≥ 0, 0 < r ≤ 2k）来表示，

给出一串数字问这串数字能有几个x表示。输出可能的长度。

题解：这题比较巧妙具体还是看代码理解一下，不好解释。

#include <iostream>

#include <cstring>

#include <vector>

#include <cstdio>

using namespace std;

typedef long long ll;

const int M = 1e5 + 10;

ll a[M];

vector<int>equ , betw , ans;//equ[i]表示a[i]中有几个2^i,betw[i]表示a[i]中有几个大于等于2^(i-1)小于2^(i)的数。ans用来存结果。

bool Is(int len) {

    vector<int>e , b;

    e = equ , b = betw;

    if(e[0] < len) return false;//如果1的数量比长度少显然不可能组成。

    b[1] += e[0] - len;//把多余的a[i]用到b[i+1]中。

    for(int i = 1 ; i < 41 ; i++) {

        if(b[i] > len) return false;//显然b[i]如果比长度还多那么也是不存在的。

        if(e[i] > len) b[i + 1] += (e[i] - len);//把多余的a[i]用到b[i+1]中。

        else if(e[i] < len) {

            b[i] -= (len - e[i]);

            b[i] = max(0 , b[i]);

            len = e[i];//由于b[i]放上去后这串数就不能再放a了所以要更新一下len

        }

        b[i + 1] += b[i];//把多余的b加上，后面可以用。

    }

    return true;

}

int main() {

    int n;

    scanf("%d" , &n);

    ans.clear() , equ.clear() , betw.clear();

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

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

    }

    int po = 0;

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

        equ.push_back(0);

        betw.push_back(0);

    }

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

        while(a[i] > ((ll)1 << po)) {

            po++;

        }

        if(a[i] == ((ll)1 << po)) {

            equ[po]++;

        }

        else {

            betw[po]++;

        }

    }

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

        if(Is(i)) {

            ans.push_back(i);

        }

    }

    if(ans.size()) {

        for(int i = 0 ; i < ans.size() ; i++) {

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

        }

    }

    else {

        printf("-1");

    }

    printf("\n");

    return 0;

}

巴特西

codeforces 807 E. Prairie Partition（贪心+思维）

最新文章

热门文章