专栏文章

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

__czl_
P13288题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miouyvfb
此快照首次捕获于
2025/12/03 01:34
3 个月前
此快照最后确认于
2025/12/03 01:34
3 个月前
查看原文

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

题目Link

思路

首先简化题意为：给定一个数 AA 和一个数组 ss，AA 可以把数组中比自己小的元素吞噬，然后自身加上这个值。有两种操作，一种是添加一个任意的数，或是删除一个现有的数，求至少多少次操作能是数组 ss 中的值被 AA全部吞噬。
考虑贪心。先对数组 ss 进行排序，定义一个变量 resres 为答案，初始为 nn，表示全部删除。先从最小的数开始尝试吞噬，能吞噬则吞噬，否则就不断往数组中增加 A−1A-1，直到可以吞噬当前的数，最后更新 ansans。
时间复杂度为 O(N×T)O(N \times T)。

Code

CPP

#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...