1812: sort
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 352 Solved: 216
SubmitStatusWeb
Board
Description
想必大家对排序已经很熟悉了，但是spy好像对排序不太熟悉，有一天，他看到这样一个关于排序的题目：
对于 k 个用空格分隔开的整数，依次为 n1, n2 … nk。请将所有下标不能被 3 但可以被 2 整除的数在这些数字原有的位置上进行升序排列，此外，将余下下标能被 3 整除的数在这些数字原有的位置上进行降序排列。
spy想了半天不知道怎么排序，你可以帮助他么？
Input
多组数据，每组数据一行，为k个小于1000的正整数，依次为 n1, n2 … nk。（1 <= k <= 100000）
Output
对于每组数据，输出排序后的结果。
Sample Input
1 3 4 2 10 6 8
Sample Output
1 2 6 3 10 4 8
代码：
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100005;
struct node {
int num;
int pos;
int flag;
node () {
flag=0;
}
}ans[maxn];
int bns[maxn],cns[maxn];
bool cmpbns(const int &a, const int &b) {
return a<b;
}
bool cmpcns(const int &a, const int &b) {
return a>b;
}
int main() {
int index,bnspos,cnspos;bnspos=cnspos=0;index=1;
while(~scanf("%d",&ans[index++].num)) {
while(getchar()!='\n') {
scanf("%d",&ans[index++].num);
}
for(int i=1;i<index;++i) {
if((i%2==0)&&(i%3!=0)) {
bns[bnspos]=ans[i].num;
ans[i].flag=-1;
ans[i].pos=bnspos;
++bnspos;
} else if(i%3==0) {
cns[cnspos]=ans[i].num;
ans[i].flag=1;
ans[i].pos=cnspos;
++cnspos;
}
}
sort(bns,bns+bnspos,cmpbns);
sort(cns,cns+cnspos,cmpcns);
for(int i=0;i<index;++i) {
if(ans[i].flag==0) continue;
else if(ans[i].flag==-1) {
ans[i].num=bns[ans[i].pos];
} else if(ans[i].flag==1) {
ans[i].num=cns[ans[i].pos];
}
}
for(int i=1;i<index-1;++i) printf("%d ",ans[i].num);
printf("%d\n",ans[index-1].num);
for(int i=1;i<index;++i) ans[i].flag=0;
cnspos=bnspos=0;index=1;
}
return 0;
}