Tree Burning

题目链接：https://atcoder.jp/contests/agc030/tasks/agc030_b

数据范围：略。

题解：

开始以为是左右左右这样，发现过不去样例。

看了样例之后，觉得是：看左边右边哪个比较长，走长的那个。

发现过了第一个样例，过不去第二个了....

看了看第二个样例，又画了画第三个样例，加上枫哥在给我这道题之前的提示：你要大胆猜啊...

发现：一定是先往一个方向连续走几个，然后左右横跳。

这个就对了，用数学归纳法容易证明。

所以我们只需要开始逆时针连续走了多少个，然后用什么前缀和啥的随便求一求就好了。

求完了之后，把序列反转再来一次即可。

代码：

#include <bits/stdc++.h>

#define N 1000010 

using namespace std;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0, f = 1;

	char c = nc();

	while (c < 48) {

		if (c == '-')

			f = -1;

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x * f;

}

ll m;

int n;

ll a[N];

ll bfr[N], ans;

void solve() {

	bfr[0] = 0;

	for (int i = 1; i <= n; i ++ ) {

		bfr[i] = bfr[i - 1] + a[i];

	}

	for (int i = 1; i <= n; i ++ ) {

		ll mdl;

		if (i & 1) {

			int x = (i - 1) >> 1;

			mdl = ((ll)m * x - (bfr[n] - bfr[n - x])) * 2 + a[n - x] + (bfr[n - x - 1] - bfr[n - x - x - 1]) * 2;

		}

		else {

			int x = i >> 1;

			mdl = (m * (x - 1) - (bfr[n] - bfr[n - x + 1])) * 2 + ((ll)m - a[n - x + 1]) + (bfr[n - x] - bfr[n - x - x]) * 2;

		}

		ans = max(ans, mdl);

	}

}

int main() {

	m = rd(), n = rd();

	for (int i = 1; i <= n; i ++ ) {

		a[i] = rd();

	}

	solve();

	for (int i = 1; i <= n; i ++ ) {

		a[i] = m - a[i];

	}

	reverse(a + 1, a + n + 1);

	solve();

	cout << ans << endl ;

	return 0;

}

巴特西

[Agc030B]Tree Burning_贪心

Tree Burning

最新文章

热门文章