「POI2017」Flappy Bird

解题思路

数据范围不小啊，离散也不行，DP不了，考虑贪心+递推。

我们递推出小鸟可以到达的高度区间。

我们发现，小鸟最好的情况就是在当前基础上，从最下方一直往下飞，或者从最上方一直往上飞。

但是这样在其他情况下不一定可行，那么我们就让它到达尽可能靠近边界的位置，也就是使得可达区间最大化。

如果在飞行过程中可达区间变为空集，那就输出无解，否则就让小鸟飞到终点的越下方越好，因为越往上花费越大。

答案的计算用到了全等三角形的相关知识，可以自己完成。

细节注意事项

咕咕咕。

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= c == '-', c = getchar();

	while (isdigit(c)) s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 500002;

int n, X, x[_], a[_], b[_];

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

	freopen("out.out", "w", stdout);

#endif

	read(n), read(X);

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

		read(x[i]), read(a[i]), read(b[i]);

	int tp = 0, bt = 0;

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

		int dis = x[i] - x[i - 1];

		if (tp + dis >= b[i])

			tp = (tp - dis - b[i]) & 1 ? b[i] - 1 : b[i] - 2;

		else tp += dis;

		if (bt - dis <= a[i])

			bt = (a[i] - bt + dis) & 1 ? a[i] + 1 : a[i] + 2;

		else bt -= dis;

		if (tp < bt) { puts("NIE"); return 0; }

	}

	printf("%d\n", (bt + x[n]) / 2);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「POI2017」Flappy Bird

解题思路

细节注意事项

参考代码

最新文章

热门文章