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

yaoyoucheng · 2025-10-12 22:36:52 · 题解

原题链接

题意概况

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

思路

我们只需要使每一次电话的距离尽可能的长。 先对每一个探测器位置从小到大排序。排序后，如果一个点大于前一个点，就把这个点减去上一个点的值统计到答案中。

我们可以使用结构体存储 p_i 与 c_i。

struct node{
    int p;
    int c;
}a[N];

然后进行排序。

int cmp(node x, node y) {
    return x.p < y.p;
} 

排序好后循环，如果发现当前的 c_i 比前一个要大，那么 ans 应当加上 c_i - c_{i - 1}。

最后输出 ans。

代码

#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。