Codeforces 1616D. Keep the Average High

本文主要是介绍Codeforces 1616D. Keep the Average High，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

题目大意

\(t(1\leq t\leq10)\) 组数据，一个长为 \(n(1\leq n\leq50000)\) 的数列，数列中每个值为 \(a_i(-10^5\leq a_i\leq10^5)\) ，一个整数 \(x(-10^5\leq x\leq10^5)\) ，求最多可以选择多少个数，使得该数列的所有区间 \([l,r](l<r)\) 满足以下两个条件中的一个：
\(1.\) 至少有 \(1\) 个数字没有被选中
\(2.\space\sum_{i=l}^ra_i\geq x(r-l+1)\)

思路

考虑第二个条件，如果我们将区间内所有数字减去 \(x\) ，那么就变为 \(\sum_{i=l}^r(a_i-x)\geq 0\) 。于是我们可以直接将数列中的全部数字先减去 \(x\) ，然后对于任意长度的区间，都可以用长度为 \(2\) 和 \(3\) 的区间拼接成，所以只需要选择的时候，所选择的所有长度为 \(2\) 和 \(3\) 的区间的和 \(\geq0\) 即可，我们进行 \(dp\)， 记录考虑到第 \(i\) 个数时最后两个位置的选择情况，判断一下如果下一个位置要被选择，新产生的长度为 \(2\) 和 \(3\) 的区间的和是否 \(\geq0\) ，进行转移即可。

代码

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using TP = tuple<int, int, int>;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2
//#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
//#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 50010;

int T, N, X, A[maxn];
int f[maxn][2][2];

void solve()
{
	for (int i = 1; i <= N; i++)
		A[i] -= X;
	f[1][0][1] = 1;
	for (int i = 2; i <= N; i++)
	{
		f[i][0][1] = max(f[i - 1][0][0], f[i - 1][1][0]) + 1;
		f[i][1][0] = max(f[i - 1][1][1], f[i - 1][0][1]);
		if (i == 2 && A[1] + A[2] >= 0)
			f[2][1][1] = 2;
		else
		{
			if (A[i] + A[i - 1] >= 0)
			{
				if (A[i] + A[i - 1] + A[i - 2] >= 0)
					f[i][1][1] = max(f[i][1][1], f[i - 1][1][1] + 1);
				f[i][1][1] = max(f[i][1][1], f[i - 1][0][1] + 1);
			}
		}
	}
	int ans = max(max(f[N][1][1], f[N][1][0]), max(f[N][0][0], f[N][0][1]));
	cout << ans << endl;
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		memset(f, 0, sizeof(f));
		cin >> N;
		for (int i = 1; i <= N; i++)
			cin >> A[i];
		cin >> X;
		solve();
	}

	return 0;
}

这篇关于Codeforces 1616D. Keep the Average High的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！