题解：P13288 [GCJ 2013 #1B] Osmos

· · 题解

题解：P13288 [GCJ 2013 #1B] Osmos

题目Link

思路

首先简化题意为：给定一个数 A 和一个数组 s，A 可以把数组中比自己小的元素吞噬，然后自身加上这个值。有两种操作，一种是添加一个任意的数，或是删除一个现有的数，求至少多少次操作能是数组 s 中的值被 A全部吞噬。

考虑贪心。先对数组 s 进行排序，定义一个变量 res 为答案，初始为 n，表示全部删除。先从最小的数开始尝试吞噬，能吞噬则吞噬，否则就不断往数组中增加 A-1，直到可以吞噬当前的数，最后更新 ans。

时间复杂度为 O(N \times T)。

Code


#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a,m[105];
int sol()
{
    cin>>a>>n;
    for(int i=1;i<=n;i++) cin>>m[i];
    sort(m+1,m+n+1);
    int ans=n,op=0;
    if(a==1) return ans;
    for(int i=1;i<=n;i++){
        while(a<=m[i]){
            a+=a-1;
            op++;
        }
        a+=m[i];
        ans=min(ans,op+n-i);
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int i=1;i<=t;i++)
        cout<<"Case #"<<i<<": "<<sol()<<'\n';
    return 0;
}