不用二分 过了30分
查看原帖
不用二分 过了30分
926630
yunxixi楼主2024/3/30 15:32

这个跳石头的题,我想的是直接记录每个石头之间的距离,然后每次搜索最短的距离,并且对数组进行更新,但是只过了30分,是这个思路不对吗?还是代码写错了

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int l, n, m;
const int N = 50010;
int nums[N];
vector<int> s;

bool cmp(int a, int b) {
	return a > b;
}

int main() {
	cin >> l >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
		s.push_back(nums[i] - nums[i - 1]);
	}
	s.push_back(l - nums[n]);

	for (int i = 0; i < m; i++) {
		int x = distance(s.begin(), min_element(s.begin(), s.end() )); //返回最小的s的下标
		if (x == n) {
			s[x - 1] += s[x];
			s.erase(s.begin() + x);
		}
		else {
			s[x + 1] += s[x];
			s.erase(s.begin() + x);
		}
	}
	int x = distance(s.begin(), min_element(s.begin(), s.end()));
	cout << s[x];

	return 0;
}
2024/3/30 15:32
加载中...