prow2012-A3-0022

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

比赛时WA得很冤枉。
排序的时候有时用下标，有时用order[i]，这种小细节很难找出来，所以以后一篇程序统一用一种方法！

{{{
#include <stdio.h>
#include <math.h>
#include <map>
#include <string>
#include <algorithm>
#include <sstream>
#include <string.h>
#include <iostream>
using namespace std;
int N,T,M;
#define maxn 1000
map<string,int> mat;
int score[maxn],point[maxn],dif[maxn],goal[maxn];
int order[maxn],glbwin[maxn],rank[maxn],glbcnt[maxn];
int cmp[maxn][maxn];
string ss[maxn];
bool CMP(int i,int j){
    return score[i]>score[j];
}
bool cmp1(int i,int j){
    i = order[i],j = order[j];
    if (point[i]!=point[j])
        return point[i]>point[j];
    else if (dif[i]!=dif[j])
        return dif[i]>dif[j];
    else //return goal[i]>goal[j];
    if (goal[i]!=goal[j])
        return goal[i]>goal[j];
    else return false;
}
bool cmp2(int i,int j){
    i = order[i],j = order[j];
    if (glbwin[i]!=glbwin[j])
        return glbwin[i]>glbwin[j];
    else if (glbcnt[i]!=glbcnt[j])
        return glbcnt[i]>glbcnt[j];
    else return rank[i]<rank[j];
}
int totcnt;
void out(int A,int B){
    if (B-A==1){
        cout<<ss[order[A]]<<endl;
        totcnt++;
        return ;
    }
    int i,j;
    int sa = A,sb = B;
    bool edit = true;

        edit = false;
        for (i=sa;i<sb;i++)
        {
            point[order[i]]= 0,dif[order[i]] = 0,goal[order[i]] = 0;
            for (j=sa;j<sb;j++)
                if (i!=j){
                    int a = i,b = j;
                    i = order[i],j = order[j];
                        if (cmp[i][j]>cmp[j][i]) point[i]+=3;
                        else if (cmp[i][j]==cmp[j][i]) point[i]+=1;
                    dif[i]+=cmp[i][j]-cmp[j][i];
                    goal[i]+=cmp[i][j];
                    i = a,j = b;
                }
            //printf("%d :%d %d %d\n",i,point[i],dif[i],goal[i]);
        }
        for (i=sa;i<sb;i++){
            for (j=i+1;j<sb;j++)
            if (cmp1(j,i)){
                swap(order[i],order[j]);
            }

        }

        for (i=sa;i<sb;){
            for (j=i+1;j<sb;j++)
                if (cmp1(i,j)||cmp1(j,i)) break;
            if (i==sa&&j==sb) break;
            out(i,j);
        //  printf("%d --- %d\n",i,j);
            i = j;
            if (i==sb) return ;
        }

    if (sa<sb-1){
        for (i=sa;i<sb;i++)
            for (j=i+1;j<sb;j++)
                if (cmp2(j,i)){
                    swap(order[i],order[j]);
                }
    }
    for (i=sa;i<sb;i++)
        cout<<ss[order[i]]<<endl,totcnt++;

}


int main(){
    bool first = true;
    while(scanf("%d\n",&N)!=EOF){
        if (first) first = false;
        else printf("\n");
        mat.clear();
        T=1;
        totcnt = 0;
        string s1,s2;
        char str[1000];
        int a,b,i,j;
        for (j=0;j<N*(N-1)/2;j++)
        {
            cin>>s1>>str>>s2;

            for (i=0;i<strlen(str);i++)
                if (str[i]==':') str[i] = ' ';
            istringstream in(str);
            in>>a>>b;
        //  cout<<s1<<"----------"<<s2<<endl;
            if (mat[s1]==0) {
                ss[T] = s1;
                mat[s1] = T++;
            }
            if (mat[s2]==0) {
                ss[T] = s2;
                mat[s2] = T++;
            }
            cmp[mat[s1]][mat[s2]] = a;
            cmp[mat[s2]][mat[s1]] = b;
        }
/*      for (i=1;i<T;i++)
            cout<<ss[i]<<endl;
        cout<<"-------------------\n"<<endl;*/
        scanf("%d\n",&M);
        for (i=0;i<M;i++){
            cin>>s1;
            if (mat[s1]!=0)
                rank[mat[s1]] = i;
        }
        for (i=1;i<=N;i++)
        {
            score[i]  =glbwin[i] = glbcnt[i] = 0;
            for (j=1;j<=N;j++)
                if(i!=j){
                    if (cmp[i][j]>cmp[j][i]) score[i]+=3;
                    else if (cmp[i][j]==cmp[j][i]) score[i]+=1;
                    glbwin[i]+=cmp[i][j]-cmp[j][i];
                    glbcnt[i]+=cmp[i][j];
                }
        }
        for (i=1;i<=N;i++)
            order[i] = i;
        sort(order+1,order+N+1,CMP);
    //  for (i=1;i<=N;i++)
    //      printf("%d\n",score[order[i]]);
        for (i=1;i<=N;){
            for (j=i+1;j<=N;j++)
                if (score[order[j]]!=score[order[i]]) break;
            out(i,j);
            i=j;
        }
        if (totcnt!=N) while(1);
    }
}
}}}

比赛时WA得很冤枉。

排序的时候有时用下标，有时用order[i]，这种小细节很难找出来，所以以后一篇程序统一用一种方法！

#include <stdio.h>
#include <math.h>
#include <map>
#include <string>
#include <algorithm>
#include <sstream>
#include <string.h>
#include <iostream>
using namespace std;
int N,T,M;
#define maxn 1000
map<string,int> mat;
int score[maxn],point[maxn],dif[maxn],goal[maxn];
int order[maxn],glbwin[maxn],rank[maxn],glbcnt[maxn];
int cmp[maxn][maxn];
string ss[maxn];
bool CMP(int i,int j){
    return score[i]>score[j];
}
bool cmp1(int i,int j){
    i = order[i],j = order[j];
    if (point[i]!=point[j])
        return point[i]>point[j];
    else if (dif[i]!=dif[j])
        return dif[i]>dif[j];
    else //return goal[i]>goal[j];
    if (goal[i]!=goal[j])
        return goal[i]>goal[j];
    else return false;
}
bool cmp2(int i,int j){
    i = order[i],j = order[j];
    if (glbwin[i]!=glbwin[j])
        return glbwin[i]>glbwin[j];
    else if (glbcnt[i]!=glbcnt[j])
        return glbcnt[i]>glbcnt[j];
    else return rank[i]<rank[j];
}
int totcnt;
void out(int A,int B){
    if (B-A==1){
        cout<<ss[order[A]]<<endl;
        totcnt++;
        return ;
    }
    int i,j;
    int sa = A,sb = B;
    bool edit = true;
        edit = false;
        for (i=sa;i<sb;i++)
        {
            point[order[i]]= 0,dif[order[i]] = 0,goal[order[i]] = 0;
            for (j=sa;j<sb;j++)
                if (i!=j){
                    int a = i,b = j;
                    i = order[i],j = order[j];
                        if (cmp[i][j]>cmp[j][i]) point[i]+=3;
                        else if (cmp[i][j]==cmp[j][i]) point[i]+=1;
                    dif[i]+=cmp[i][j]-cmp[j][i];
                    goal[i]+=cmp[i][j];
                    i = a,j = b;
                }
            //printf("%d :%d %d %d\n",i,point[i],dif[i],goal[i]);
        }
        for (i=sa;i<sb;i++){
            for (j=i+1;j<sb;j++)
            if (cmp1(j,i)){
                swap(order[i],order[j]);
            }
        }
        for (i=sa;i<sb;){
            for (j=i+1;j<sb;j++)
                if (cmp1(i,j)||cmp1(j,i)) break;
            if (i==sa&&j==sb) break;
            out(i,j);
        //  printf("%d --- %d\n",i,j);
            i = j;
            if (i==sb) return ;
        }
    if (sa<sb-1){
        for (i=sa;i<sb;i++)
            for (j=i+1;j<sb;j++)
                if (cmp2(j,i)){
                    swap(order[i],order[j]);
                }
    }
    for (i=sa;i<sb;i++)
        cout<<ss[order[i]]<<endl,totcnt++;
}
int main(){
    bool first = true;
    while(scanf("%d\n",&N)!=EOF){
        if (first) first = false;
        else printf("\n");
        mat.clear();
        T=1;
        totcnt = 0;
        string s1,s2;
        char str[1000];
        int a,b,i,j;
        for (j=0;j<N*(N-1)/2;j++)
        {
            cin>>s1>>str>>s2;
            for (i=0;i<strlen(str);i++)
                if (str[i]==':') str[i] = ' ';
            istringstream in(str);
            in>>a>>b;
        //  cout<<s1<<"----------"<<s2<<endl;
            if (mat[s1]==0) {
                ss[T] = s1;
                mat[s1] = T++;
            }
            if (mat[s2]==0) {
                ss[T] = s2;
                mat[s2] = T++;
            }
            cmp[mat[s1]][mat[s2]] = a;
            cmp[mat[s2]][mat[s1]] = b;
        }
/*      for (i=1;i<T;i++)
            cout<<ss[i]<<endl;
        cout<<"-------------------\n"<<endl;*/
        scanf("%d\n",&M);
        for (i=0;i<M;i++){
            cin>>s1;
            if (mat[s1]!=0)
                rank[mat[s1]] = i;
        }
        for (i=1;i<=N;i++)
        {
            score[i]  =glbwin[i] = glbcnt[i] = 0;
            for (j=1;j<=N;j++)
                if(i!=j){
                    if (cmp[i][j]>cmp[j][i]) score[i]+=3;
                    else if (cmp[i][j]==cmp[j][i]) score[i]+=1;
                    glbwin[i]+=cmp[i][j]-cmp[j][i];
                    glbcnt[i]+=cmp[i][j];
                }
        }
        for (i=1;i<=N;i++)
            order[i] = i;
        sort(order+1,order+N+1,CMP);
    //  for (i=1;i<=N;i++)
    //      printf("%d\n",score[order[i]]);
        for (i=1;i<=N;){
            for (j=i+1;j<=N;j++)
                if (score[order[j]]!=score[order[i]]) break;
            out(i,j);
            i=j;
        }
        if (totcnt!=N) while(1);
    }
}