MT3026 砍玉米

本文主要是介绍MT3026 砍玉米，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

样例1：

 输入：

6
1 3
4 2
5 1
7 8
19 10
30 2

输出：

6

其中1<=n<=10^5,1<=xi,hi<=10^9

思路：贪心：从左到右或者从右到左依次判断每一棵玉米是否可以倒下

（以从左到右为例：先往左倒，若不能左倒则往右倒）

因为最左侧玉米一定可以往左倒，最右侧玉米一定可以往右倒，所以两种顺序都可以

先左后右：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, ans;
int x[N], h[N];int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> x[i] >> h[i];}int temp = -0x3f3f3f3f; // 负无穷for (int i = 0; i < n; i++){if (x[i] - h[i] > temp)//往左倒{ans++;temp = x[i];}else if (x[i] + h[i] < x[i + 1])//往右倒{ans++;temp = x[i] + h[i];}else{temp = x[i];}}ans++;cout << ans;return 0;
}

先右后左：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, ans;
int x[N], h[N];int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> x[i] >> h[i];}int temp = 0x3f3f3f3f; // 正无穷for (int i = n; i >= 0; i--){if (x[i] + h[i] < temp) // 往右倒{ans++;temp = x[i];}else if (x[i] - h[i] > x[i - 1]) // 往左倒{ans++;temp = x[i] - h[i];}else{temp = x[i];}}ans++;cout << ans;return 0;
}

这篇关于MT3026 砍玉米的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---