【题意】现在有几个球排成一排，编号从1开始，开始时所有球为黑色，现在有n（<=2000）次操作，每次操作将l[i]至r[i]（均在int范围）的球凃成颜色c[i]（黑色'b'或白色'w'），然后找到最长的连续白色球，输出左右端点符号
【离散化】因为l[i]和r[i]都在int范围，显然不不可以开一个2^31-1那么大的数组。将l[i]和r[i]+1离散化，再模拟染色即可。
如果你不知道离散化：
将l[i]数组所有数与r[i]+1数组所有数取出来从小到大排序，做一个映射。
如样例
3
1 4 w
8 11 w
3 5 b
把1、5、8、12、3、6取出来，排序为1、3、5、6、8、12，离散化后
|
原数 |
1 |
3 |
5 |
6 |
8 |
12 |
|
离散化后 |
0 |
1 |
2 |
3 |
4 |
5 |
用mp[]做映射，类型为mp<int,int>。rev_mp[int]做逆向映射。
比如mp[4]=8，离散化后的4就可以看成数8,9,10,11的集合。如果离散化后的4被染成白色，那么相当于原数8,9,10,11均被染成白色。
再取样例中的一行： 1 4 w作为例子，这里1,4是原数，要从把球1,2,3,4均涂色，显然是凃离散化后0（1,2）和1（3,4）即可。
如果当初把r[i]做离散化而不是r[i]+1做离散化的话，r[i]就表示从它开始几个数的集合都被涂色，而不是从它结束涂色。
做好映射后，2^31-1个数就可以看成最多2*n个数，然后模拟染色即可。
这道题写的好晕啊，WA了5发后发现是多Case输入。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include<set> 7 #include<map> 8 #include<stack> 9 #include<vector> 10 #include<queue> 11 #include<string> 12 #include<sstream> 13 #define eps 1e-9 14 #define FOR(i,j,k) for(int i=j;i<=k;i++) 15 #define MAXN 1005 16 #define MAXM 40005 17 #define INF 0x3fffffff 18 using namespace std; 19 typedef long long LL; 20 int i,j,k,n,m,x,y,T,ans,big,cas,num; 21 bool flag; 22 map <int , int> mp; 23 set <int> st; 24 25 int l[8005],r[8005],rev_mp[8010]; 26 char c[8005],color[8010]; 27 int main() 28 { 29 while(~scanf("%d",&n)) 30 { 31 st.clear(); 32 mp.clear(); 33 for (i=1;i<=n;i++) 34 { 35 scanf("%d %d %c",&l[i],&r[i],&c[i]); 36 st.insert(l[i]);//现将其压入set中，也可以放入数组中最后排序 37 st.insert(r[i]+1); 38 } 39 40 num=0; 41 for (set <int> ::iterator it=st.begin();it!=st.end();it++)//离散化 42 { 43 mp[*it]=num;//mp为map<int,int>类型，做一个映射，如上边的表格 44 rev_mp[num]=*it;//这是map的逆向映射。 45 46 num++; 47 } 48 49 for (i=0;i<num;i++) color[i]='b';//初始时为全部黑色 50 51 for (i=1;i<=n;i++)//模拟涂刷过程 52 { 53 int left=mp[l[i]]; 54 int right=mp[r[i]+1]; 55 for (j=left;j<right;j++) 56 { 57 color[j]=c[i]; 58 } 59 } 60 61 int pre=0; 62 int left,right; 63 flag=false; 64 ans=0; 65 for (i=1;i<num;i++)//扫一遍寻找最长的连续白色球 66 { 67 if (color[i]!=color[i-1]) 68 { 69 if (color[i]=='w') 70 { 71 pre=i;//左端点 72 }else 73 if (color[i-1]=='w' && ans < rev_mp[i] - rev_mp[pre] ) 74 { 75 ans=rev_mp[i]-rev_mp[pre];//找到答案记录一下。 76 left=rev_mp[pre]; 77 right=rev_mp[i]-1; 78 flag=true; 79 } 80 } 81 } 82 if (!flag) printf("Oh, my god ");else 83 printf("%d %d ",left,right); 84 } 85 return 0; 86 } 87