猪八戒吃西瓜(wmelon)-排序-查找
<center>
提交: 30 解决: 14
[提交][状态][讨论版] </center>
问题 A: 猪八戒吃西瓜(wmelon)
时间限制: 1 Sec 内存限制: 64 MB提交: 30 解决: 14
[提交][状态][讨论版] </center>
题目描述
有一天，贪吃的猪八戒来到了一个大果园，果园里有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[100002]; 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[100002]; long int m; long int cou=0; scanf("%ld",&n); for(long int i=1;i<=n;i++){ scanf("%ld",&a[i]); } qsort(a+1,n,sizeof(long int),comp); scanf("%ld",&m); for(long int i=1;i<=m;i++){ scanf("%ld",&xigua[i].k); xigua[i].kcinw=i; } sort(xigua+1,xigua+m+1,cmp); long int i=1; long int j=1; while(1){ if(j==m+1){ break; } if(a[i]==xigua[j].k){ //printf("%ld\n",i); xigua[j].ksortw=i; j++; }else{ i++; } } sort(xigua+1,xigua+m+1,cmp2); for(int i=1;i<=m;i++){ printf("%d\n",xigua[i].ksortw); } return 0; }
网易有道公司氛围 38人发布