Educational Codeforces Round 69 (Rated for Div. 2)

A. DIY Wooden Ladder

排个序，最长的两根作梯子的腿，然后答案就是 剩余梯子的个数，梯子腿长度-1。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
int a[100005];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		sort(a, a + n);
		int ans = min(a[n - 2] - 1, n - 2);
		printf("%d\n", ans);
	}
}

B. Pillars

找到最大值，左右扫

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
int a[200005];
int main()
{
	int n;
	scanf("%d", &n);
	int maxn = 0, f = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		if (maxn < a[i])
		{
			maxn = a[i];
			f = i;
		}
	}
	for (int i = f; i > 1; i--)
	{
		if (a[i - 1] > a[i])
		{
			printf("NO");
			return 0;
		}
	}
	for (int i = f; i < n; i++)
	{
		if (a[i] < a[i + 1])
		{
			printf("NO");
			return 0;
		}
	}
	printf("YES");
}

C. Array Splitting

维护差分数组，排个序，最大的k个不选。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
int a[300005];
ll sum;
int main()
{
	vector<ll>v;
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	if (k == n)
	{
		printf("0");
		return 0;
	}
	ll ans = 0;
	for (int i = 2; i <= n; i++)
	{
		v.push_back(a[i] - a[i - 1]);
		sum += a[i] - a[i - 1];
	}
	sort(v.begin(), v.end(), [](ll q, ll w) {
		return q > w;
		});
	for (int i = 0; i < k - 1; i++)
	{
		sum -= v[i];
	}
	printf("%lld", sum);
}

D. Yet Another Subarray Problem

1、枚举起点的余数，从起点的余数开始每m个数字为一段，将每段的第一个数字减去k.

2、对于每一个位置，计算一下以这个点为终点所获得的价值。

3、由于起点的余数已经确定（枚举），所以在每一段的开始，更新前面的所有段能取到的最小前缀和。

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[300005];
int main()
{
	int n, m, k;
	ll res = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	for (int i = 0; i < m; i++)
	{
		ll sum = 0, minn = 0;
		for (int j = i; j < n; j++)
		{
			if (j % m == i)
			{
				minn = min(minn, sum);
				sum -= k;
			}
			sum += a[j];
			res = max(res, sum - minn);
		}
	}
	printf("%lld\n", res);
}