1324：【例6.6】整數區間

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 7185 ??? 通過數: 4260

【題目描述】

請編程完成以下任務：

1.讀取閉區間的個數及它們的描述；

2.找到一個含元素個數最少的集合，使得對于每一個區間，都至少有一個整數屬于該集合，輸出該集合的元素個數。

【輸入】

首行包括區間的數目n，1≤n≤10000，接下來的n行，每行包括兩個整數a,b，被一空格隔開，0≤a≤b≤10000，它們是某一個區間的開始值和結束值。

【輸出】

第一行集合元素的個數，對于每一個區間都至少有一個整數屬于該區間，且集合所包含元素數目最少。

【輸入樣例】

4 3 6 2 4 0 2 4 7

【輸出樣例】

2

【分析】

? ? ? ? 算法模型∶給 n個閉區間 [ai, bi]，在數軸上選盡量少的點，使每個區間內至少有一個點。
? ? ? ? 算法：首先按 b1<=b2<=…<=bn 排序。每次標記當前區間的右端點 x，并右移當前區間指針，直到當前區間不包含 x，再重復上述操作。如下圖，如果選灰色點，移動到黑色點更優。

【輸出樣例】

#include <stdio.h> #define N 10010 struct point {int x;int y; }a[N],t;int main() {int i,j,x,sum=0,n;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);for(i=0;i<n-1;i++) //比較排序 {for(j=i+1;j<n;j++){if(a[i].y>a[j].y){t=a[i];a[i]=a[j];a[j]=t;}}}x=-1;for(i=0;i<n;i++){if(x>=a[i].x)continue; //貪心,如果當前區間包含標記點，就跳過sum++;x=a[i].y;}printf("%d\n",sum); //更新標記點 return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1324

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1324：【例6.6】整数区间）的全部內容，希望文章能夠幫你解決所遇到的問題。

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