113
技術社區[雲棲]
NYOJ891-找點
找點
時間限製：2000 ms | 內存限製：65535 KB
難度：2
描述
上數學課時，老師給了LYH一些閉區間，讓他取盡量少的點，使得每個閉區間內至少有一個點。但是這幾天LYH太忙了，你們幫幫他嗎？
輸入
多組測試數據。
每組數據先輸入一個N，表示有N個閉區間（N≤100)。
接下來N行，每行輸入兩個數a，b(0≤a≤b≤100），表示區間的兩個端點。
輸出
輸出一個整數，表示最少需要找幾個點。
樣例輸入
4
1 5
2 4
1 4
2 3
3
1 2
3 4
5 6
1
2 2
樣例輸出
1
3
1
來源
原創
思路：
貪心算法
1.先對區間按照右邊界從小到大排序
2.每次取區間的左邊界最大值和右邊界最小值，如果兩個區間剛好相鄰，取他們的相交點作為左右邊界，
隻要每次新的區間的左邊界不大於等於原來的右邊界，取點總數都不用加1，否則加1
例如：
6
3 4
2 4
3 10
7 9
8 11
8 14
排序後是：
2 4
3 4
7 9
3 10
8 11
8 14
過程：sum=1;
首先，模板為[2,4]，3,4加入， 比較左右點，更新為[3,4]，此時依舊sum=1;
然後，模板為[3,4]，7,9加入， 發現7>4， 此時更新左右邊界為[7,9],sum+1=2;
然後，模板為[7,9]，3,10加入，比較左右點，無需更新，此時依舊sum=2；
然後，模板為[7,9]，8,11加入，比較左右點，更新為[8,9]，此時依舊sum=2；
然後，模板為[8,9]，8,14加入，比較左右點，不更新，此時sum依舊為2
最終答案便是2
圖：
AC代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}a[200];
int cmp(node a,node b)
{
if(a.y!=b.y) return a.y<b.y;
}
int main()
{
int i,j,n,m1,m2,sum,x;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
sort(a,a+n,cmp);
m1=a[0].x;m2=a[0].y;sum=1;x=0;
//printf("m1=%d m2=%d\n",m1,m2);
for(i=1;i<n;i++)
{
if(a[i].x<m2&&a[i].x>m1)
m1=a[i].x;
else
{
if(a[i].x==m2)
{
m1=a[i].x;
m2=a[i].x;
}
if(a[i].x>m2)
{
sum++;
m1=a[i].x;
m2=a[i].y;
}
}
//printf("m1=%d m2=%d\n",m1,m2);
}
printf("%d\n",sum);
}
return 0;
}
最後更新：2017-04-03 12:56:36