NOI1997 競賽排名 competitionsort 解題報告

【題目描述】
題目網上都有，比如說http://www.byvoid.com/blog/noi-1997-solution/ 。

【分析】

這是道NOI中的水題，簡單的模擬即可，只需要看清楚題目中給的糾結的式子即可。最後需要結構體的三級排序。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Student
{
public:
    int G[9];
    double Sum;
    double Pos[9];
    double SumP;
    int n;
}S[1001];
int N;
double Av[8];


double Abs(double n)
{
    if(n>0)
        return n;
    return -n;
}

void Averge(int I)
{
    int Tot=0;
    for (int i=1;i<=N;i++)
        Tot+=S[i].G[I];
    double TT=Tot;
    double NN=N;
    Av[I]=TT/NN;
}

bool flag=true;

void print()
{
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=8;j++)
            cout<<S[i].G[j]<<" ";
        cout<<" "<<S[i].Sum<<" "<<S[i].SumP<<" "<<S[i].n<<endl;
    }
    cout<<endl;
    for (int i=1;i<=8;i++)
        cout<<Av[i]<<" ";
   }

void Position(int I)
{
    for (int k=1;k<=8;k++)
    {
        double E=0;
        for (int i=1;i<=N;i++)
        {
            double Tmp;
            Tmp=S[i].G[k];
            E+=( Abs(Tmp-Av[k])  );
        }
       
        if(E==0)
        {
            S[I].Pos[k]=0;
            continue;
        }
       
        /*計算Xij-AVGj*/
        double Xij;
        double Up;
        double Down;
        Xij=S[I].G[k];
        Up=Xij-Av[k];
        Down=E/N;
        S[I].Pos[k]=Up/Down;
    }
   
    double Sp=0;
    for (int i=1;i<=3;i++)
        Sp+=S[I].Pos[i];
   
    for (int i=4;i<=8;i++)
        Sp+=(S[I].Pos[i]*0.8);
    S[I].SumP=Sp;
    return;
}

int cmp(const void *a,const void *b)
{
    class Student *c=(class Student *)a;
    class Student *d=(class Student *)b;
    if(c->SumP!=d->SumP)
    {
        if(d->SumP>=c->SumP)
            return 1;
        else
            return -1;
    }
    else
    {
        if(c->Sum!=d->Sum)
            return d->Sum>c->Sum?1:-1;
        else
            return c->n-d->n;
    }
}

  
void init()
{
    scanf("%d\n",&N);
    
    for (int i=1;i<=N;i++)
    {
        int Tmp=0;
        for(int j=1;j<=8;j++)
        {
            cin>>S[i].G[j];
            Tmp+=S[i].G[j];
        }
        S[i].Sum=Tmp;
        S[i].n=i;
    }
   
    for (int i=1;i<=8;i++)
        Averge(i);
    for (int i=1;i<=N;i++)
        Position(i);
    qsort(S+1,N,sizeof(S[0]),cmp);
    return;
}


int main()
{
    freopen("competitionsort.in","r",stdin);
    freopen("competitionsort.out","w",stdout);
    init();
    //print();
    if(!flag)
        return 0;
    for (int i=1;i<=N;i++)
        cout<<S[i].n<<endl;
    return 0;
}