河工大萌新赛E 聚会
作者:
caibiddc
,
2022-07-19 16:12:34
,
所有人可见
,
阅读 234
https:
题目转换后的问题其实就是 题目所给数字组成的可重复数字集合的子集和组成的集合中未出现的最小正整数
有点抽象 举一个例子 比如 1 2 5 6 7 这几个数字不能组成4 所以要找的数就是4 再比如 2 3 4 5 6 这几个数字无论如何组合也不能等于1 所以1就是要找的数
刚开始可能想到要用解决背包dp的思想 但是ai<=1e9 果断放弃
大致思路就是 先把所有数字从小到大排序 然后假定最小的数是1(0+1) 进入循环判断 如果1存在 那么就假定最小的数字为2(1+1) 如果2也存在 那么就假定数字为4(1+2+1) 不判断3是因为3一定存在(1和2相加为3)
如果循环中有3 则判断3+3+1 没3 有4 则判断3+4+1 每次进入新的一次循环其实就可以把之前的数字都忘掉 当作是一次全新的循环 比如 最小整数为先为3 后为7 中间的 4 5 6 不用考虑 因为如果能组成7 那么一定能组成4 5 6 代码很简单
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i];
}
sort(a,a+n);
long long sum=0;
for(int i=0; i<n; i++)
{
if(a[i]<=sum+1) sum+=a[i];
else break;
}
cout<<sum+1;
}