题目大意就是给n个数,任意组合,求n以内最小的不能组成的数,解题思路用的是动态规划的思想,先排序,维护一个区间[ 1 , sum ] ,表示该区间内的数都可以组成,如果当前a[ i ]大于sum + 1 , 当前sum + 1就是当前不能组成的数,因为当前a[ i ] 已经大于sum + 1,无论如何都无法组成sum + 1;相反,如果a[ i ]小于等于sum + 1,则更新sum = sum + a[i],此时区间为[1,sum + a[ i ] ] ,为什么sum + 1 到 sum + a[i]可以取到,这是因为[ 1 , sum ] 中的值我们是能取到的。
具体代码如下:
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 998244353;;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1, 0);
// vector<int> dp(n+1,0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a.begin() + 1, a.end());
int sum = 0;
for (int i = 1; i <= n; ++i) {
if(a[i] > sum + 1){
cout<<sum+1<<endl;
return;
}
sum += i;
}
if(sum < n){
cout<<sum + 1<<endl;
return;
}
cout << "Cool!" << endl;
}
signed main() {
//ios::sync_with_stdio(false);cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}

京公网安备 11010502036488号