#include<iostream.h>
struct circletype
{
    int length;
    int smallest;
    int weight;
    circletype *next;
};
int arr[100],ord[100];
void additem(circletype **p,int l,int s,int w)
{
    circletype *q=new circletype;
    q->length=l;q->smallest=s;q->weight=w;
    q->next=*p;
    *p=q;
}
void destroy(circletype **p)
{
    circletype *q;
    while(*p)
    {
        q=(*p)->next;
        delete *p;
        *p=q;
    }
}
void ssort(int *ord,int n)
{
    int i,j,t;
    for(i=0;i<n-1;++i)
    {
        for(t=i,j=i+1;j<n;++j)if(ord[j]<ord[t])t=j;
        if(t!=i){j=ord[t];ord[t]=ord[i];ord[i]=j;}
    }
}
int pos(int *ord,int p,int n)
{
    int i;
    for(i=0;i<n;++i)
        if(ord[i]==p)return i;
    return -1;
}
void getcircles(circletype **cir,int n)
{
    int i;
    char *v=new char[n];
    for(i=0;i<n;++i)v[i]=0;
    for(i=0;i<n;++i)
    {
        if(v[i])continue;
        int p,q=i;
        int l=0,s=0x7fff,w=0;
        do
        {
            p=arr[q];if(p<s)s=p;w+=p;
            ++l;
            v[q]=1;q=pos(ord,p,n);
        }while(q!=i);
        additem(cir,l,s,w);
    }
    delete[]v;
}
int root(circletype *cir,int m)
{
    int s=0,t1,t2;
    while(cir)
    {
        if(cir->length>1)
        {
            if((t1=(cir->length-2)*cir->smallest)>(t2=cir->length*m+cir->smallest*2))
                s+=t2;
            else s+=t1;
            s+=cir->weight;
        }
        cir=cir->next;
    }
    return s;
}
int min(int n)
{
    int t=0;
    for(int i=1;i<n;++i)if(arr[i]<arr[t])t=i;
    return arr[t];
}
int main()
{
    circletype *head=NULL;
    int n,i;
    while(1)
    {
        cin>>n;
        if(n==0)break;
        for(i=0;i<n;++i){cin>>arr[i];ord[i]=arr[i];}
        ssort(ord,n);
        getcircles(&head,n);
        cout<<root(head,min(n))<<endl;
        destroy(&head);
    }
    return 0;
}


怎么还是WrongAnswer???我觉得这样是对的。。。

rickone我加入你们队了，ac到底，hehe

各位写回帖的
写程序的时候不喜欢加点注释吗？
你不加注释以为自己有多厉害吗？
在厉害也只是散兵游勇
难登大雅之堂
而且
鲁迅说得好
无端的耽误别人的时间就是谋财害命
老实说
我觉得你们的行为就是这样子的~！

请问搂主所编程序所用的思想是什么，可以告知一下吗？

是不是每进行一次扫描，找出相邻两数之和最小的且逆序的交换，重复进行这个过程，直到完成排序。是不是这样？如果是这样，又该用什么理论证明呢？