找點(diǎn)

時(shí)間限制：2000 ms ?|? 內(nèi)存限制：65535 KB 難度：2 描述

上數(shù)學(xué)課時(shí)，老師給了LYH一些閉區(qū)間，讓他取盡量少的點(diǎn)，使得每個(gè)閉區(qū)間內(nèi)至少有一個(gè)點(diǎn)。但是這幾天LYH太忙了，你們幫幫他嗎？

輸入

多組測(cè)試數(shù)據(jù)。
每組數(shù)據(jù)先輸入一個(gè)N，表示有N個(gè)閉區(qū)間（N≤100)。
接下來(lái)N行，每行輸入兩個(gè)數(shù)a，b(0≤a≤b≤100），表示區(qū)間的兩個(gè)端點(diǎn)。

輸出

輸出一個(gè)整數(shù)，表示最少需要找?guī)讉€(gè)點(diǎn)。

樣例輸入

4 1 5 2 4 1 4 2 3 3 1 2 3 4 5 6 1 2 2

樣例輸出

1 3 1

來(lái)源

原創(chuàng)

上傳者

TC_李遠(yuǎn)航

剛開始很不明白，但是畫了幾個(gè)數(shù)據(jù)就知道怎么回事了

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAX 100010 struct node {int l,r; }edge[MAX]; int vis[MAX]; int cmp(node s1,node s2) {if(s1.r==s2.r)return s1.l<s2.l;return s1.r<s2.r; } int main() {int n;while(scanf("%d",&n)!=EOF){memset(vis,0,sizeof(vis));for(int i=0;i<n;i++)scanf("%d%d",&edge[i].l,&edge[i].r);sort(edge,edge+n,cmp);int cnt=edge[0].r,sum=1;for(int i=1;i<n;i++){if(edge[i].l>cnt){cnt=edge[i].r;sum++;}}printf("%d\n",sum);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/playboy307/p/5273730.html

總結(jié)

以上是生活随笔為你收集整理的nyoj--891--找点（贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。