【CodeForces】CF545C. Woodcutters【贪心】

题意

一条路上有树，树有高度h，我们可以将树向左或向右砍倒只要它倒下去不会压到其他树（不论这些树是站着还是倒下了）

求最多可以砍倒多少树

思路

贪心，第1个数左倒,第n个树右倒,剩下的树优先左倒即可。

AC代码

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")#includeusing namespace std;#define x first
#define y secondtypedef long long ll;
typedef pair<int, int> p;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;int a[maxn];
int h[maxn];int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i] >> h[i];if (n <= 2) cout << n << endl;else {int ans = 2;for (int i = 2; i <= n - 1; i++) {if (a[i] - h[i] > a[i - 1]) ans++;else if (a[i] + h[i] < a[i + 1]) {a[i] += h[i];ans++;}}cout << ans << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！