Codeforces Round #822 (Div. 2) A - D补题

比赛传送门：Dashboard - Codeforces Round #822 (Div. 2) - Codeforces

A. Select Three Sticks

枚举所有点，选择一个点作为基准，计算所有点与基准的差的绝对值，取最小的三个相加，再从所有结果中取小就可以了。时间复杂度\(O(t*n^2*logn)\)

B. Bright, Nice, Brilliant

这个构造太简单就不说了。

C. Removing Smallest Multiples

从1到N枚举所有数字x，再枚举这个数字x的所有倍数，如果遇到了要保留的数字（s[i] == ‘1’），那么就break，因为这个要保留的数字是x的最小倍数，无法被删除，后面也就无法删除了。类似于埃氏筛法。

调和级数\(\sum_{1}^{n}1 / i =ln(n) + y\)，复杂度为\(O(t* n * logn)\)。

D. Slime Escape

先假定要从K到0，如果是要到N + 1只需要将序列反过来从N - K + 1到0即可。

我们把K右侧的点作为“补给站”，但是要求sum要大于等于一个阈值才能获取这个补给，然后一直往左边走，看看能不能走到终点、

反转数组改变起点再算一次。

这是一个很重要的思维，左右横跳的题可以转化为“补给站”。

代码 / Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int maxn = 2e5 + 9, inf = 8e18;

int a[maxn], N, K;

bool go(int k)
{
	vector<pair<int, int> > v;//补给站数组 
	for(int i = k + 1, sum = 0, mi = 0;i <= N; ++ i)//mi是过程中的代价，要减去mi依然非负才可以加上sum 
	{
		sum += a[i], mi = min(mi, sum);
		if(sum > 0)v.push_back({mi, sum}), mi = sum = 0;
	}
	
	for(int i = k - 1, j = 0, sum = a[k];i >= 1; -- i)//sum是过程中的值 
	{
		while(j < v.size() && sum + v[j].fi >= 0)sum += v[j ++].second;
		sum += a[i];
		if(sum < 0)return false;//如果中途出现负数就停 
	}
	return true;
}

void solve()
{
	cin >> N >> K;
	
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	bool ans1 = go(K);
	reverse(a + 1,a + 1 + N);
	bool ans2 = go(N - K + 1);
	
	cout << ((ans1 || ans2) ? "YES" : "NO") << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}