找點

時間限制：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 貪心算法！類似：噴水裝置(二)、外星人的供給站、非洲小孩 AC碼： #include<stdio.h> #include<algorithm> using namespace std; struct node {int left,right;int sum; }num[105]; int cmp(node a,node b) {return a.sum<b.sum; } int main() {int n,i,len,count;while(~scanf("%d",&n)){for(i=0;i<n;i++){scanf("%d%d",&num[i].left,&num[i].right);num[i].sum=num[i].left*1000+num[i].right;}sort(num,num+n,cmp);len=num[0].right;count=1;for(i=1;i<n;i++){if(num[i].left>len){count++;len=num[i].right;}if(num[i].right<len)len=num[i].right;}printf("%d\n",count);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 891 找点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。