18.2.27 codevs1214 线段覆盖

题目描述 Description

给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

输入描述 Input Description

输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述 Output Description

输出第一行是一个整数表示最多剩下的线段数。

样例输入 Sample Input

6 3

1 3

2 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

0<N<100

 1 #include <iostream>
 2 #include <math.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int n;
10     cin>>n;//共n条线段
11     int line[150][3];//存两端点
12     for(int i=1;i<=n;i++)
13     {
14         cin>>line[i][1]>>line[i][2];
15         if(line[i][1]>line[i][2])
16         {
17             int tmp=line[i][1];
18             line[i][1]=line[i][2];
19             line[i][2]=tmp;
20         }
21     }
22     int bef=-1000,sum=0;
23     while(1)
24     {
25         int min=1000,minn=0,flag=0;
26         for(int i=1;i<=n;i++)
27         {
28             if(line[i][2]<min&&line[i][1]>=bef)//符合条件的最优解
29             {
30                 min=line[i][2];
31                 minn=i;
32                 flag=1;
33             }
34         }
35         if(!flag)
36             break;
37         bef=line[minn][2];
38         sum++;
39 
40     }
41     cout<<sum<<endl;
42     return 0;
43 }

View Code

基本典型的贪心

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。