题目大意就是给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; }