样例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;
}