一道离散化的题目.
灰常猥琐的边界, 导致我WA#3又WA#9又WA#13又WA#14才AC.
所谓离散化, 就是把原先最傻的hash表变小.
因为我们只用到题目中的某些点, 那么用这些点为坐标, 记录颜色情况就好了.
注意边界: 0 和 10^9.
推荐事先放到表里, 这样就不用做边界了.
我做到WA#14才发现这个问题, 没法改了, 大家凑合看吧.
#include<iostream> using namespace std; const int MAX=1000000000; int A[5010][3]; int T[10010],has[10010]; int n,len,node; char s[5]; int bisearch(int i) { int l=0,r=len,mid; while(l<=r) { mid=(l+r)>>1; if(T[mid]==i) return mid; else if(T[mid]>i) r=mid-1; else l=mid+1; } return 0; } void sort(int l,int r) { int i,j,temp; if(l>=r) return; i=l; j=r; temp=T[i]; while(i<j) { while(i<j&&T[j]>=temp) j--; T[i]=T[j]; while(i<j&&T[i]<=temp) i++; T[j]=T[i]; } T[i]=temp; sort(l,i-1); sort(i+1,r); return; } int main() { int i,j; int l,r,min=0,temp=0,flag; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d%s",&A[i][1],&A[i][2],s); T[len++]=A[i][1]; T[len++]=A[i][2]; if(s[0]=='w') A[i][0]=0; else A[i][0]=1; } sort(0,len); node=-1; for(i=1;i<=len;i++) if(T[i]!=T[i-1]) T[++node]=T[i]; len=node+1; T[len]=MAX; has[len]=1; for(i=0;i<n;i++) { l=bisearch(A[i][1]); r=bisearch(A[i][2]); for(j=l;j<r;j++) has[j]=A[i][0]; } if(has[0]==1) if(T[0]!=0) { min=T[0];flag=T[0]; } else { for(i=1;i<len;i++) if(has[i]) break; min=T[i]; flag=T[i]; } for(i=0;i<len;i++) { if(!has[i]) temp+=T[i+1]-T[i]; else { if(temp>min) { min=temp; flag=T[i]; } temp=0; } } if(MAX-T[len]+temp>min) { min=MAX-T[len]+temp; flag=MAX;} printf("%d %d/n",flag-min,flag); return 0; }
