题目链接

题意

给你\(n\)个数，每个数表示\(\frac{1}{2^{a_i}}\)，要你把这\(n\)个数分为两堆，使得每堆的和都大于等于\(\frac{1}{2}\)。

思路

首先我们假设第一堆的下标为\(x_1,x_2\dots,x_n\)，且\(2^{a_{x_1}}\leq 2^{a_{x_2}}\leq\dots\leq 2^{a_{x_n}}\)，则：

\[\begin{aligned}
&\sum\limits_{i=1}^{n}\frac{1}{2^{a_{x_i}}}&\\
=&\sum\limits_{i=1}^{n}\frac{2^{a_{x_n}-a_{x_i}}}{2^{a_{x_n}}}\text{（通分）}&
\end{aligned}
\]

我们知道\(2\)个\(2^x\)构成一个\(2^{x+1}\)，因此我们确定每一堆分母的最大值后按照\(2^{a_{x_i}}\)从小到大来凑\(2^{a_{x_n}-1}\)。

注意，一旦相邻两个数的大小差值大于等于\(17\)就直接不用取输出\(NO\)，因为\(2^{17}\geq 10^5\)，后面不管怎么凑都是不可能凑出我们所需要的数的。

代码实现如下

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <cassert>

#include <iostream>

#include <algorithm>

#include <unordered_map>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson rt<<1

#define rson rt<<1|1

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("D://Code//in.txt","r",stdin)

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

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int maxn = 1e5 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int t, n;

int vis[maxn];

struct node {

    int val, id;

    bool operator < (const node& x) const {

        return val < x.val;

    }

}a[maxn];

int main() {

#ifndef ONLINE_JUDGE

FIN;

#endif // ONLINE_JUDGE

    scanf("%d", &t);

    int icase = 0;

    while(t--) {

        scanf("%d", &n);

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

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

            a[i].id = i;

            vis[i] = 0;

        }

        printf("Case %d: ", ++icase);

        sort(a + 1, a + n + 1);

        LL nw;

        if(a[1].val == 1) {

            vis[a[1].id] = 1;

        } else {

            nw = a[1].val - 1;

            if(nw >= 17) {

                printf("NO\n");

                continue;

            }

            nw = (1<<nw) - 1;

            vis[a[1].id] = 1;

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

                if(nw == 0) break;

                if(a[i].val == a[i-1].val) --nw, vis[a[i].id] = 1;

                else {

                    if(a[i].val - a[i-1].val >= 17) {

                        break;

                    }

                    nw = nw * (1<<(a[i].val - a[i-1].val)) - 1;

                    if(nw > n - i) break;

                    vis[a[i].id] = 1;

                }

            }

            if(nw != 0) {

                printf("NO\n");

                continue;

            }

        }

        int idx = -1;

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

            if(!vis[a[i].id]) {

                idx = i;

                break;

            }

        }

        if(idx == -1) {

            printf("NO\n");

            continue;

        }

        if(a[idx].val == 1) {

            printf("YES\n");

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

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

            }

            printf("\n");

        } else {

            nw = a[idx].val - 1;

            if(nw >= 17) {

                printf("NO\n");

                continue;

            }

            nw = (1<<nw) - 1;

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

                if(nw == 0) break;

                if(vis[a[i].id]) continue;

                if(a[i].val == a[i-1].val) --nw;

                else {

                    if(a[i].val - a[i-1].val >= 17) {

                        break;

                    }

                    nw = nw * (1<<(a[i].val - a[i-1].val)) - 1;

                    if(nw > n - i) break;

                }

            }

            if(nw != 0) {

                printf("NO\n");

                continue;

            }

            printf("YES\n");

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

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

            }

            printf("\n");

        }

    }

    return 0;

}

巴特西

Justice(HDU6557+2018年吉林站+二进制）

题目链接

题意

思路

代码实现如下

最新文章

热门文章