【问题描述】

有 n 堆硬币依次排列，每一堆有 a_i 个。每堆硬币全是真币或全是假币，真币每个重 5 克，假币每个重 4 克。你有一台电子天平，可以从每堆硬币中挑出若干个进行一次称量（也可以一个都不选）。现在你想要知道，若要确定前 1,2,……,n 堆硬币的真假，至少要称量几次。

【输入】

第一行一个整数 n，表示硬币的堆数。
接下来一行 n 个整数 a_i，表示每堆硬币的数量。

【输出】

n 行，每行一个整数，第 i 行表示想要确定前 i 堆硬币的真假至少要称量几次。

【样例 1】

3
2 3 4

1
1
1

【样例 1 解释】

以前三堆硬币为例，分别取出 1、2、4 枚硬币，则一次称量的结果即可确定三堆的真假。

【数据范围】

对于 10%的数据，n≤1
对于 30%的数据，n≤2
对于 60%的数据，n≤100
对于 80%的数据，n≤1000
对于 100%的数据，n≤10^5，a_i≤10^9
存在 10%的数据，a_i=1

思路

可以发现每次选取的是2^0-2^n,因此要每次称得最多,因此按照最大能放的2的幂次分类,从后往前扫,用平均的思想

代码

#include <bits/stdc++.h>
using namespace std;

int n,cnt[45],k[45],tag,ans,y,mt;
long long tmp;
void add(long long t){
    for (int i=32;i>=0;--i){
        if (t&(1LL<<i)){
            cnt[i]++;
            mt=max(mt,i);
            break;
        }
    }
}

int ch(int x,int y){
    int ret=x/y;
    if (x%y!=0) ret++;
    return ret;
}

int main(){
    freopen("coins.in","r",stdin);
    freopen("coins.out","w",stdout);
    cin>>n;
    if (n==1){
        cout<<1<<endl;
        return 0;
    }
    for (int i=1;i<=n;++i){
        scanf("%lld",&tmp);
        add(tmp);
        int sum=0,ans=0;
        for (int j=0;j<=mt;++j){
            sum+=cnt[j];
            ans=max(ans,ch(sum,j+1));
        }
        printf("%d\n",ans);
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/50/