又来求救了~~算法排序OK的进来帮帮忙啊！！有分拿！
在学校的在线测试系统ACM遇到了一道题了，提交后结果《答案50%错误》，来求救了~~下面是题目和我的代码~~如果有更好的方法更快的方法也可以发来看看，思路也好，题目的意思是输入给数组，然后给数组的数排名次，从小到大，相同的数字一样名次，我的代码也在下面~~
题目描述：
输入一个数组的值,求出各个值从小到大排序后的次序。并且要求相同的数据其序号是相同的
输入：
输入有多组数据。
每组输入的第一个数为数组的长度n(1<=n<=10000),后面的数为数组中的值,以空格分割。
输出：
各输入的值按从小到大排列的次序(最后一个数字后面没有空格)。
样例输入
4
-3 75 12 -3
样例输出
1 3 2 1
[code=C/C++][/code]
#include<iostream>
using namespace std;
int main()
{
int n,a[10000],b[10000],x=0,temp;
cin>>n;
while(x<n)
{
cin>>a[x];
b[x]=a[x];
x++;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
if(a[j]==a[j+1])
{
a[j+1]=2147483646;
}
}
}
for(int i2=0;i2<n;i2++)
{
for(int j2=0;j2<n-1;j2++)
{
if(b[i2]==a[j2])
{
if(i2==0)
cout<<j2+1;
else
cout<<" "<<j2+1;
}
}
}
return 0;
}
[code=C/C++][/code]
[解决办法]
#include <iostream>#include <algorithm>using namespace std;struct Node { int num; int oldIndex; int newIndex;}NOdeArray[10000];bool cmpNum(Node x,Node y){ return x.num<y.num;} bool cmpOldIndex(Node x,Node y){ return x.oldIndex<y.oldIndex;} int main(){ int n,m; cin>>n; for (int i = 0 ;i < n; i++) { cin>>m; NOdeArray[i].oldIndex = i; NOdeArray[i].num = m; } sort(NOdeArray,NOdeArray+n,cmpNum); int index = 1; NOdeArray[0].newIndex = index; for (int i = 1 ;i < n; i++) { if (NOdeArray[i-1].num == NOdeArray[i].num) { NOdeArray[i].newIndex = NOdeArray[i-1].newIndex; }else NOdeArray[i].newIndex = ++index; } sort(NOdeArray,NOdeArray+n,cmpOldIndex); for (int i = 0 ;i < n; i++) { cout<<NOdeArray[i].newIndex; if(i != n-1) cout<<" "; } return 0;}
[解决办法]
又是我~呵呵
做ACM，尽可能多用现有的工具来减少编码量，否则累死你。最简单易用的就属STL了，强大，易学，易用。
基本思路应该是，排序，查序
所以：
#include <iostream>#include <vector>#include <algorithm>#include <map>;using namespace std;int main() { int count; cin>>count; vector<int> nums(count); for (int i=0; i<count; ++i) { cin>>nums[i]; } // 保留一份拷贝，以备后面查顺序用 vector<int> originNums = nums; // 对原始数据进行排序 sort(nums.begin(), nums.end()); // 去除数据中重复的内容 vector<int>::iterator newEnd = unique(nums.begin(), nums.end()); nums.erase(newEnd, nums.end()); // 对排序后数据进行序号标识 map<int,int> orders; int order = 1; for (vector<int>::iterator it=nums.begin(); it!=nums.end(); ++it) { orders[*it] = order++; } // 利用已序标识，输出原始数据的序号 for (vector<int>::iterator it=originNums.begin(); it!=originNums.end(); ++it) { cout<<orders[*it]<<' '; } return 0;}
[解决办法]
#include <stdio.h>#include <algorithm>using namespace std;struct node{ int data; int pos; int order;};node p[10000];bool cmp1(const node &a,const node &b){ return a.data<b.data;}bool cmp2(const node&a,const node &b){ return a.pos<b.pos;}int main(){ int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { scanf("%d",&p[i].data); p[i].pos=i; } sort(p,p+n,cmp1); int order=1; p[0].order=order++; for(int i=1;i<n;i++) { if(p[i].data==p[i-1].data) p[i].order=p[i-1].order; else p[i].order=order++; } sort(p,p+n,cmp2); for(int i=0;i<n-1;i++) printf("%d ",p[i].order); printf("%d\n",p[n-1].order); }}