小A是一个游戏爱好者,他对游戏里的等级有着奇怪的执念。现在他知道游戏服务器里的玩家编号与等级(游戏的等级上限是100),他想要你根据等级从小到大输出玩家编号。
输入格式:
输入共三行。
第一行输入一个正整数N(N≤3×106)
第二行输入N个正整数a1,a2,...,aN, 其中ai(ai≤109)表示第i个玩家的编号
第三行输入N个正整数b1,b2,...,bN, 其中bi(1≤bi≤100)表示第i个玩家的等级
数据保证没有两个玩家拥有相同的编号。
请注意:由于输入输出数据规模过大,请尽可能使用scanf/printf等较快的输入输出方式。
输出格式:
根据等级从小到大输出玩家编号, 若等级一致,则根据输入的先后顺序输出玩家编号, 以换行作为分割。
输入样例:
5
123123 321321 2222 1 3
1 1 100 3 2
输出样例:
123123
321321
3
1
2222
存在bug的代码:(数据量非常大的时候会运行超时)
#include<bits/stdc++.h>
using namespace std;
struct node{
int id;
int bian;
int grade;
}a[3000001];
bool cmp( node a,node b){
if(a.grade!=b.grade)
return a.grade<b.grade;
else return a.id<b.id;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
a[i].id=i;
scanf("%d",&a[i].bian);
}
for(int i=0;i<n;i++){
scanf("%d",&a[i].grade);
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
printf("%d\n",a[i].bian);
}
}
AC代码:
思路:玩家等级很小编号很大数据规模N也很大,这个时候可以使用桶排序,用一个vector<int> v[N]来记录, v[i]存储等级为i的玩家的编号。
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> v[101], a, b;
int n;
scanf("%d", &n);
for(int i = 0;i < n; i++) {//编号
int x;
scanf("%d", &x);
a.push_back(x);
}
for(int i = 0;i < n; i++) {//等级
int x;
scanf("%d", &x);
b.push_back(x);
}
for(int i = 0;i < n; i++)
v[b[i]].push_back(a[i]);
for(int i = 1;i <= 100; i++)//v[i]在这里相当于是一个二维数组 有元素就输出x
for(int x : v[i]) printf("%d\n", x);
return 0;
}