SGU 133 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=133

133. Border

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Along the border between states A and B there are N defence outposts. For every outpost k, the interval [Ak,Bk] which is guarded by it is known. Because of financial reasons, the president of country A decided that some of the outposts should be abandoned.In fact, all the redundant outposts will be abandoned. An outpost i is redundant if there exists some outpost j such that Aj < Ai and Bi < Bj. Your task is to find the number of redundant outposts.

在 A 和 B 的边界出有 N 个前哨站.对于每一个前哨站 k,他的管辖范围 [Ak,Bk] 是已知的.由于经济原因,A 国总统决定减少一些前哨站.多余的前哨站都会被抛弃.我们定义 i 号前哨站是多余的如果存在另一个前哨战 j 满足 Aj < Ai 且 Bi < Bj.你的任务是计算多余的前哨站个数.

Input

The first line of the input will contain the integer number N (1 <=N <= 16 000). N lines will follow, each of them containing 2 integers:Ak and Bk (0 <= Ak < Bk <= 2 000 000 000), separated by blanks. All the numbers Ak will be different. All the numbers Bk will be different.

第一行是整数N (1 <=N <= 16 000).接下来N行每行包含2个整数: Ak 和 Bk (0 <= Ak < Bk <= 2 000 000 000),空格隔开.所有的 Ak 都是不同的,所有的 Bk 也是不同的.

Output

You should print the number of redundant outposts.

输出多余的前哨站个数.

Sample Input

5
0 10
2 9
3 8
1 15
6 11

Sample Output

3

CODE

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 
struct node
{
  int a,b;
}D[16005];
 
bool cmp(node x,node y)
{
  return x.a<y.a;
}
 
int main()
{
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;++i)
    scanf("%d%d",&D[i].a,&D[i].b);
  sort(D,D+n,cmp);
  int l=D[0].a,r=D[0].b,cnt=0;
  for(i=1;i<n;++i)
    {
      if(D[i].b<=r)
	++cnt;
      else
	r=D[i].b;
    }
  printf("%dn",cnt);
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>