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

· · 题解

题目传送门

题意

给定街道上 n 个探测器位置和检测到的通话次数，求实际可能的最小总通话次数。每个通话必须跨越至少一个探测器。

思路

考虑贪心。

我们要使总通话次数最小，应尽可能让每次通话覆盖多个探测器。所以对探测器按位置从小到大排序后，相邻探测器之间的通话次数差值即为必须新增的通话数。具体来说，当前探测器的通话数若大于前一个，则差值部分必须由新的通话贡献。

AC CODE

/*
writer:akaryan
*/
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Int __int128
#define db double
#define ldb long double
#define inf (1 << 30)
#define INF (1LL << 60LL)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define sz(x) ((int)x.size())
#define bug puts("----------")
using namespace std;
const int N = 2e5 + 10 , M = 2e5 + 10; 
const int mod = 998244353;
ll n , m , ans;//十年OI一场空，不开long long见祖宗！别问我是怎么知道的
struct Node{
    ll x , y;
}a[N];
inline void solve(){
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i].x >> a[i].y;
    sort(a + 1 , a + n + 1 , [&](const Node &x , const Node &y){return x.x < y.x;});//排序
    for (int i = 1 ; i <= n ; i ++) if (a[i].y >= a[i - 1].y) ans += a[i].y - a[i - 1].y;
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    solve();
    return 0;
}