关于今天的"超级码力在线编程大赛初赛"T1
  • 板块题目总版
  • 楼主明依
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/8/29 12:02
  • 上次更新2023/11/5 14:02:44
查看原帖
关于今天的"超级码力在线编程大赛初赛"T1
155826
明依楼主2020/8/29 12:02

我的做法:先处理出相邻两棵树之间的距离,放入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;
}
2020/8/29 12:02
加载中...