ZJU 2956Another Horizontally Visible Segments

作者在 2008-05-02 19:14:21 发布以下内容

http://acm.zju.edu.cn/show_problem.php?pid=2956

这道题很郁闷啊 ,当时题目居然看错了,一开始的时候是理解对的 ,后来发现x输入怎么一点用都没有的,就开始郁闷了,这道题有这么难么??都怪自己审题不清,还不肯重新看题。。。。

#include<stdio.h>
#include<string.h>
int count[10001];
int main()
{
 int T,n,i,x[4001],y1[4001],y2[4001],sum,max;
 scanf("%ld",&T);
 while (T--)
 {
  scanf("%d",&n);
  memset(count,0,sizeof(count));
  for (i=0;i<n;++i)
  {
   scanf("%d%d%d",&x[i],&y1[i],&y2[i]);
   count[y1[i]]++,count[y2[i]+1]--;
  }   
  sum=0;
  max=0;
  for (i=0;i<10001;++i)
  {
   sum=sum+count[i];
   if (sum>max)
   {
    max=sum;
   }
  }
  printf("%d\n",max);
  
 }
 return 0;
}

ACM | 阅读 2444 次
文章评论,共4条
狂人老大(作者)
2008-05-04 10:58
1
<div class="xspace-quote">原帖由BCCN 网友于2008-05-03 20:46:22发表
请问count[]作用是什么,这是动态规划吗?</div>
呵呵  不是动态规划的   这个是开始的时候++   这个结果由sum来实现记忆功能     结束的时候--    从而实现在y1到y2的记录过程。。。。。
狂人老大(作者)
2008-05-05 09:38
2
<div class="xspace-quote">原帖由BCCN 网友于2008-05-04 14:59:21发表
好厉害,其实好像还是有点不明白,呵呵你是怎么想到用这个方法的啊?</div>
呵呵  也没什么的啦  都是学过来的方法而已   不过我感觉这个确实是个好方法  本来是用另一种方法也行的  就是在每次的y1到y2之间都进行++     最后对数组进行扫描一次   得到最大的那个就是结果了
狂人老大(作者)
2008-05-13 09:05
3
<div class="xspace-quote">原帖由BCCN 网友于2008-05-12 19:49:25发表
弱弱的问句。。。这题目什么意思。。</div>
在坐标系中,有一系列线段与横坐标垂直,并且这些直线的x坐标相异。线段的上坐标为y2,下坐标为y1。求:从左到右划一条直线,最多可以与多少条线段相交?
呵呵  我们学校的人在比赛的时候好多人都看错题目了   哎。。。。
狂人老大(作者)
2008-05-15 09:31
4
<div class="xspace-quote">原帖由BCCN 网友于2008-05-14 19:57:40发表
很不错的算法:)</div>
呵呵  谢谢
游客请输入验证码
最新评论