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

· · 题解

题目传送门

正文开始

阅读理解：

有 m 个住户，n 个探测器，第 i 个探测器在位置 a_i，两个住户之间可以连一条线段，线段经过的探测器都会触发，现给出每个探测器的位置和触发次数，求最少能有几条线。

思路

不难发现，要想要线数量少，就应该每一条线能经过的探测器尽可能多。

但是如果暴力枚举，复杂度是 O(n^2)，会超时，需要简化。

很显然，在对位置进行排序后，探测器的触发次数是呈上图趋势，可以看成是由一个个“小山丘”组成的，单拎一个“小山丘”出来，我们能发现，这个“小山丘”的最长线数量就是在“山峰”之前的每个点与上一个点的高度差之和。把这个发现应用到每一个“小山丘”上，这个问题就解决了。

代码：

代码也非常好写，如果这个点大于前一个点，就把这个点减去上一个点的值统计到答案中。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
struct node{int x,s;}a[1005];//x是位置，s是值 
inline bool cmp(node p,node q){return p.x<q.x;}
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].x>>a[i].s;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
        if(a[i].s>a[i-1].s)ans+=a[i].s-a[i-1].s;
    cout<<ans;
    return 0;
}