正文开始

阅读理解：

有

m

个住户，

n

个探测器，第

i

个探测器在位置

a_i

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

思路

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

但是如果暴力枚举，复杂度是

O(n^2)

，会超时，需要简化。

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

代码：

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

CPP

#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;
}

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

文章操作

正文开始

阅读理解：

思路

代码：

相关推荐

评论

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