题意：有一个字典序名单，现在把这些名单的顺序和名字的字符顺序扰乱了，要输出原先的名字在原来的名单中的最低和最高位置。
分析：先将所有的名字串按字典序从小到大和从大到小分别排序smin[]和smax[]，然后将名单按从小到大和从大到小分别排序x[]和y[]。
枚举smin[i]，在y[]中查找第一个比smin[i]大于或等于的名字串，其位置j就是在原来的名单中的最低位置了；
枚举smax[i],如果在x[i]中能查找到第一个与smax[i]相等的名字串，则其位置j就是在原来的名单中的最高位置了，
如果没有相等的，那么找第一个比smax[i]大的名字串，其位置j-1就是在原来的名单中的最高位置了。
查找的时候用二分就行了。
AC代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 char smin[50010][30],smax[50010][30]; 6 bool cmp1(char a,char b) 7 { 8 return a<b; 9 } 10 bool cmp2(char a,char b) 11 { 12 return a>b; 13 } 14 struct node{ 15 char str[30]; 16 bool operator <(const node &a)const{ 17 return strcmp(str,a.str)<0; 18 } 19 }x[50010],y[50010]; 20 int binary(char s[],node a[],int n,int flag) 21 { 22 int low=1,high=n,mid; 23 while(low<=high) 24 { 25 mid=(low+high)>>1; 26 if(strcmp(s,a[mid].str)==0) 27 return mid; 28 else if(strcmp(s,a[mid].str)>0) 29 low=mid+1; 30 else 31 high=mid-1; 32 } 33 if(flag==1) 34 return low; 35 else 36 return high; 37 } 38 int main() 39 { 40 int n,i; 41 char s[30]; 42 scanf("%d",&n); 43 for(i=1;i<=n;i++) 44 { 45 scanf("%s",s); 46 strcpy(smin[i],s); 47 sort(smin[i],smin[i]+strlen(s),cmp1); 48 strcpy(x[i].str,smin[i]); 49 50 strcpy(smax[i],s); 51 sort(smax[i],smax[i]+strlen(s),cmp2); 52 strcpy(y[i].str,smax[i]); 53 } 54 sort(x+1,x+1+n); 55 sort(y+1,y+1+n); 56 /* for(i=1;i<=n;i++) 57 printf("%s\n",x[i].str); 58 for(i=1;i<=n;i++) 59 printf("%s\n",y[i].str);*/ 60 for(i=1;i<=n;i++) 61 { 62 int low=binary(smin[i],y,n,1); 63 int high=binary(smax[i],x,n,2); 64 printf("%d %d\n",low,high); 65 } 66 return 0; 67 }