SWJTU 2208 最大覆盖

最大覆盖

Time Limit:1000MS Memory Limit:32768K
Total Submit:20 Accepted:7

Description

我们定义一条线段，首先可以认为它在X轴上，它的起点为(a,0)终点为(b,0)，所以我们可以简化成[a,b]。现在我们有N条这样的线段都位于X轴上，所以肯定存在一点被覆盖多次或者一次，我们的任务就是找到最多被覆盖的次数，请参考样例便于理解。

Input

第一行输入为一个整数N(1≤N≤10^5),表示我们有N条线段，接下来的N行每行包括两个整数a,b(1≤a≤b≤10^9)表示线段的起点和终点。

Output

输出一个整数表示被覆盖的最大次数。

Sample Input

Sample Output

3
1

Hint

对于第一组我们可以发现2被覆盖次数最多为3次,依次被[1 2],[2 2],[2 4]这三条线段覆盖,所以输出为3。
对于第二组最大覆盖次数为1且1 2 3都被覆盖1次，所以输出1。

思路：先扫描思想

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<numeric>
13 #include<cmath>
14 #include<stdlib.h>
15 #include<vector>
16 #include<stack>
17 #include<set>
18 #define FOR(x, b, e)  for(int x=b;x<=(e);x++)
19 #define REP(x, n)     for(int x=0;x<(n);x++)
20 #define INF 1e7
21 #define MAXN 100010
22 #define maxn 1000010
23 #define Mod 1000007
24 #define N 1010
25 using namespace std;
26 typedef long long LL;
27 
28 
29 bool flag[N], a[N][N];
30 int ans, cnt[N], group[N], n, m, vis[N];
31 bool dfs(int u, int pos){
32     int i, j;
33     for (i = u + 1; i <= n; i++){
34         if (cnt[i] + pos <= ans) return 0;
35         if (a[u][i]){
36             // 与目前团中元素比较，取 Non-N(i) 
37             for (j = 0; j < pos; j++) if (!a[i][vis[j]]) break;
38             if (j == pos){     // 若为空，则皆与 i 相邻，则此时将i加入到 最大团中 
39                 vis[pos] = i;
40                 if (dfs(i, pos + 1)) return 1;
41             }
42         }
43     }
44     if (pos > ans){
45         for (i = 0; i < pos; i++)
46             group[i] = vis[i]; // 最大团 元素 
47         ans = pos;
48         return 1;
49     }
50     return 0;
51 }
52 
53 void maxclique()
54 {
55     ans = -1;
56     for (int i = n; i > 0; i--)
57     {
58         vis[0] = i;
59         dfs(i, 1);
60         cnt[i] = ans;
61     }
62 }
63 
64 int main(){
65     int T;
66     scanf("%d", &T);
67     while (T--){
68         scanf("%d%d", &n, &m);
69         int x, y;
70         memset(a, 0, sizeof(a));
71         for (int i = 0; i < m; i++){
72             scanf("%d%d", &x, &y);
73             a[x][y] = a[y][x] = 1;
74         }
75         for (int i = 1; i <= n; i++)
76             for (int j = 1; j <= n; j++)
77                 if (i == j) a[i][j] = 0;
78                 else    a[i][j] ^= 1;
79                 maxclique();
80 
81                 if (ans < 0) ans = 0;
82                 printf("%d
", ans);
83                 for (int i = 0; i < ans; i++)
84                     printf(i == 0 ? "%d" : " %d", group[i]);
85                 if (ans > 0) puts("");
86     }
87     return 0;
88 }

代码君