我的做法:先处理出相邻两棵树之间的距离,放入b数组,然后扫描b数组,用cnt来表示目前已经连续统计了cnt个距离,用tot来统计这连续cnt个距离之和。如果tot>=d,那么ans+=cnt-1.循环结束时,如果tot不为0,那么ans+=cnt,最后返回ans。
求大佬hack一下QAQ,不知道哪里错了
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, ans;
int a[N], b[N];
class Solution {
public:
/**
* @param trees: the positions of trees.
* @param d: the minimum beautiful interval.
* @return: the minimum number of trees to remove to make trees beautiful.
*/
int treePlanning(vector<int> &trees, int d) {
n = trees.size();
m = n - 1;
for (int i = 0; i < n; ++i) a[i + 1] = trees[i];
for (int i = 1; i < n; ++i) b[i] = a[i + 1] - a[i];
int cnt = 0, tot = 0;
for (int i = 1; i <= m; ++i) {
tot += b[i];
++cnt;
if (tot >= d) {
ans += cnt - 1;
cnt = 0;
tot = 0;
}//合并这些
}
if (tot) {//没有合并完
ans += cnt;
}
return ans;
}
};
vector <int> v;
int main () {
int m, n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
v.push_back(x);
}
scanf("%d", &m);
//虽然原题中没有输入n,但是为了调试代码
//我还是加入了n.各位只需要看那个函数即可
Solution A;
cout<<A.treePlanning(v, m);
return 0;
}