专栏文章

题解：P7260 [COCI 2009/2010 #3] RAZGOVOR

yyaoyoucheng
P7260题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minmfvz8
此快照首次捕获于
2025/12/02 04:48
3 个月前
此快照最后确认于
2025/12/02 04:48
3 个月前
查看原文

原题链接

题意概况

有 mm 个住户，nn 个探测器，探测器在 pip_i 的位置上，为了使通话数最小，不难想到本题贪心的思路。

思路

我们只需要使每一次电话的距离尽可能的长。 先对每一个探测器位置从小到大排序。排序后，如果一个点大于前一个点，就把这个点减去上一个点的值统计到答案中。
我们可以使用结构体存储 pip_i 与 cic_i。
CPP
struct node{
	int p;
	int c;
}a[N];
然后进行排序。
CPP
int cmp(node x, node y) {
	return x.p < y.p;
}
排序好后循环，如果发现当前的 cic_i 比前一个要大，那么 ansans 应当加上 ci−ci−1c_i - c_{i - 1}。
最后输出 ansans。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 100;
struct node{
	int p;
	int c;
}a[N];
int n, m, ans;
int cmp(node x, node y) {
	return x.p < y.p;
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].p >> a[i].c;
	} 
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		if (a[i].c > a[i - 1].c) {
			ans += a[i].c - a[i - 1].c; 
		}
	}
	cout << ans;
	return 0;
}
最后再提醒一下，记得看数据开 long long。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...