问题 A: 猪八戒吃西瓜(wmelon)
时间限制: 1 Sec 内存限制: 64 MB
提交: 30 解决: 14
[提交][状态][讨论版]
题目描述
有一天，贪吃的猪八戒来到了一个大果园，果园里有n(n≤100000)个大西瓜，每个西瓜 的质量不大于长整型(longint)，并且每个西瓜的质量都不同。猪八戒非常无聊，先把所有的西瓜按从小到大排列，然后再选m(m≤l00000)个质量是Ki的西瓜，请你帮他把想吃的西瓜找出来。
输入
第1行输入n，然后以下n行输入n个整数；
接着输入m，然后以下m行，每行一个整数Ki。
输出
输出m行，每行一个整数，表示重新排列后，Ki在这N个数中的位置。
样例输入
3
132
123
145
1
123
样例输出
1
解题思路：距离上一次做题已经一星期了，主要是因为题做不下去了，基础太弱，稍微复杂点的算法题就做不出来了，由于心比较浮躁，算法也看不懂。。。要时刻提醒自己：保持一颗平静的心！！
这个题里面的输出说：表示重新排列后，ki在里面的位置，让我误以为每取一次后面的数字都得减1！！！然后提交两遍不对。
然后zxp提醒后，改完提交AC了。
由于数据量太多，不能每取一个就查找一次，那样即使用二分查找也得nlogn，也是比较大的。
最好的方法是只查找一次：将查找的数字从小到大排序，然后从已排好序的西瓜里开始找，找到一个后接着从上一个的位置开始找就可以，这样时间复杂度是n；
例：西瓜： 2 3 5 7 8 9 设置一个i；
要查找的排好序： 3 8 设一个j；
j=1的时候，i从1到3所在下标；j=2时，i从3的下标到8的下标，查找完后i从1到n；
然后再按输入顺序排序，输出排序后的下标即可。 代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib> using namespace std; struct node{
long int k;
long int ksortw;
long int kcinw;
};
node xigua[]; int comp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
} int cmp(node a,node b){
return a.k<b.k;
} int cmp2(node a,node b){
return a.kcinw<b.kcinw;
} int main()
{
long int n;
long int a[];
long int m; long int cou=;
scanf("%ld",&n);
for(long int i=;i<=n;i++){
scanf("%ld",&a[i]);
}
qsort(a+,n,sizeof(long int),comp);
scanf("%ld",&m);
for(long int i=;i<=m;i++){
scanf("%ld",&xigua[i].k);
xigua[i].kcinw=i;
}
sort(xigua+,xigua+m+,cmp);
long int i=;
long int j=;
while(){
if(j==m+){
break;
}
if(a[i]==xigua[j].k){
//printf("%ld\n",i);
xigua[j].ksortw=i;
j++;
}else{
i++;
}
}
sort(xigua+,xigua+m+,cmp2);
for(int i=;i<=m;i++){
printf("%d\n",xigua[i].ksortw);
} return ;
}