Div.2 CF1129B题(贪心，构造)

题目链接：https://codeforces.com/contest/2277/problem/B

题目大意：一个非负整数数组，若能通过反复操作（选全正连续子数组全部减1，再从中删去一个元素）最终变为全0数组，则为“好数组”。目标：给定数组a，求其“好子序列”的最大长度

题目思路：如果数组a在最大长度的情况下都不能通过以上操作成为好数组，更短的情况下一定不成立，那么可以知道好子序列的长度要么是a数组本身的长度，要么是0，我们可以对要求简化一下：如果最终数组只要有一个0且唯一存在那么就是好数组，所以我们直接找出数组a中最小的元mn，如果mn<a数组长度，假如 mn=4 a.size=5,说明我们最多有四次操作机会(排除最小数本身)去让mn–并删除出mn以外的元素，此时就只有mn这一个元素了，并且为0，符合题意，而对于其他mn=3，2，1，0等情况，由于我们只需保留一个0就行，其他元素在操作中删除就行了，而mn>=a,就不能通过有效操作使得mn变为0

时间复杂度:O(n)

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define endl "\\n"
using ll = long long;
using ld = long double;
/*
https://codeforces.com/contest/2277/problem/B
Div.2 CF1129B题(贪心，构造)
题目大意：一个非负整数数组，若能通过反复操作（选全正连续子数组全部减1，再从中删去一个元素）最终变为全0数组，则为“好数组”。
目标：给定数组a，求其“好子序列”的最大长度

题目思路：如果数组a在最大长度的情况下都不能通过以上操作成为好数组，更短的情况下一定不成立，
那么可以知道好子序列的长度要么是a数组本身的长度，要么是0，我们可以对要求简化一下：
如果最终数组只要有一个0且唯一存在那么就是好数组，所以我们直接找出数组a中最小的元素mn，
如果mn<a数组长度，假如 mn=4 a.size=5,说明我们最多有四次操作机会(排除最小数本身)去让mn–并删除出mn以外的元素，
此时就只有mn这一个元素了，并且为0，符合题意，而对于其他mn=3，2，1，0等情况，由于我们只需保留一个0就行，
其他元素在操作中删除就行了，而mn>=a,就不能通过有效操作使得mn变为0
*/
//时间复杂度:O(n)
void solve()
{
int n;
cin >> n;
vector<int> a(n);
int mn = 1e9;//初始化最小值
for (int i = 0; i < n; i++)
{
cin >> a[i];
mn = min(mn, a[i]);//找到最小值
}
if (mn < n)
{
cout << n << endl;
}
else
{
cout << 0 << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T–)
{
solve();
}
return 0;
}