题意:有一个字典序名单,现在把这些名单的顺序和名字的字符顺序扰乱了,要输出原先的名字在原来的名单中的最低和最高位置。

分析:先将所有的名字串按字典序从小到大和从大到小分别排序smin[]和smax[],然后将名单按从小到大和从大到小分别排序x[]和y[]。

枚举smin[i],在y[]中查找第一个比smin[i]大于或等于的名字串,其位置j就是在原来的名单中的最低位置了;

枚举smax[i],如果在x[i]中能查找到第一个与smax[i]相等的名字串,则其位置j就是在原来的名单中的最高位置了,

如果没有相等的,那么找第一个比smax[i]大的名字串,其位置j-1就是在原来的名单中的最高位置了。

查找的时候用二分就行了。

AC代码:

 #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char smin[][],smax[][];
bool cmp1(char a,char b)
{
return a<b;
}
bool cmp2(char a,char b)
{
return a>b;
}
struct node{
char str[];
bool operator <(const node &a)const{
return strcmp(str,a.str)<;
}
}x[],y[];
int binary(char s[],node a[],int n,int flag)
{
int low=,high=n,mid;
while(low<=high)
{
mid=(low+high)>>;
if(strcmp(s,a[mid].str)==)
return mid;
else if(strcmp(s,a[mid].str)>)
low=mid+;
else
high=mid-;
}
if(flag==)
return low;
else
return high;
}
int main()
{
int n,i;
char s[];
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%s",s);
strcpy(smin[i],s);
sort(smin[i],smin[i]+strlen(s),cmp1);
strcpy(x[i].str,smin[i]); strcpy(smax[i],s);
sort(smax[i],smax[i]+strlen(s),cmp2);
strcpy(y[i].str,smax[i]);
}
sort(x+,x++n);
sort(y+,y++n);
/* for(i=1;i<=n;i++)
printf("%s\n",x[i].str);
for(i=1;i<=n;i++)
printf("%s\n",y[i].str);*/
for(i=;i<=n;i++)
{
int low=binary(smin[i],y,n,);
int high=binary(smax[i],x,n,);
printf("%d %d\n",low,high);
}
return ;
}
05-11 02:46