team2012-F3-sol-0022
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
题意：一个小组有n支队伍，两两之间进行一场球赛，现在知道每场的结果和排名规则，求最后的排名
规则英文写的好坑啊。。到最后才发现题意理解错了-_-##
规则按优先顺序：
s) 首先按照分数排序，每场赢者得3分，平则各一分
a) 按照平分的队伍集合中两两之间的比赛获得的分数排序
b) 按这个集合中比赛获得的净胜球的累积排序。。不是最大一场净胜球。。-_-###
c) 按这个集合中比赛的进球数排序
d) 对于tie的情况反复应用abc直到没作用
e) 按总净胜球的累积排序。。不是最大一场净胜球。。-_-###
f) 按总进球数排序
g) 按一个ranklist排序
解法：递归排序即可。。
}}}
{{{
#include <iostream>
#include <map>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
const int MAXN = 505;
map<string, int> num;
bool vis[MAXN][MAXN];
string s1, s2, s3;
int n, m, score[MAXN], diff[MAXN][MAXN], goal[MAXN][MAXN], rank[MAXN];
int lst[MAXN], pts[MAXN][MAXN], e_diff[MAXN], e_goal[MAXN], e_pts[MAXN];
int t_goal[MAXN], t_diff[MAXN], tot;
string name[MAXN];
int get_n(string& s)
{
if(num[s] == 0)
{
num[s] = ++tot;
name[tot] = s;
}
return num[s];
}
void init()
{
int a = get_n(s1),
b = get_n(s3),
ga, gb;
for(int i=0;i<s2.size();i++)
if(s2[i] == ':')
s2[i] = ' ';
istringstream in(s2);
in>>ga>>gb;
if(ga > gb)
{
pts[a][b] = 3;
pts[b][a] = 0;
}
if(gb > ga)
{
pts[b][a] = 3;
pts[a][b] = 0;
}
if(ga == gb)
pts[a][b] = pts[b][a] = 1;
score[a] += pts[a][b];
score[b] += pts[b][a];
goal[a][b] = ga;
goal[b][a] = gb;
diff[a][b] = ga-gb;
diff[b][a] = gb-ga;
t_goal[a] += ga;
t_goal[b] += gb;
t_diff[a] += diff[a][b];
t_diff[b] += diff[b][a];
}
bool abc(int a, int b)
{
if(e_pts[a] != e_pts[b]) return e_pts[a] > e_pts[b];
if(e_diff[a] != e_diff[b]) return e_diff[a] > e_diff[b];
return e_goal[a] > e_goal[b];
}
bool efg(int a, int b)
{
if(t_diff[a] != t_diff[b]) return t_diff[a] > t_diff[b];
if(t_goal[a] != t_goal[b]) return t_goal[a] > t_goal[b];
return rank[a] > rank[b];
}
bool sco(int a, int b)
{
return score[a] > score[b];
}
void gao(int l, int r)
{
if(vis[l][r])
{
sort(lst+l, lst+r+1, efg);
return;
}
vis[l][r] = 1;
for(int i=l;i<=r;i++)
{
int a = lst[i];
e_pts[a] = e_diff[a] = e_goal[a] = 0;
}
for(int i=l;i<=r;i++)
for(int j=l;j<=r;j++)
{
int a = lst[i], b = lst[j];
if(a != b)
{
e_pts[a] += pts[a][b];
e_diff[a] += diff[a][b];
e_goal[a] += goal[a][b];
}
}
sort(lst+l, lst+r+1, abc);
while(l < r)
{
int p = l;
while(p+1<=r && abc(lst[l], lst[p+1])==0) p++;
if(p > l) gao(l, p);
l = p+1;
}
}
int main()
{
int cs = 0;
while(cin>>n)
{
if(cs++) cout<<endl;
num.clear();
tot = 0;
memset(score, 0, sizeof(score));
memset(t_goal, 0, sizeof(t_goal));
memset(t_diff, 0, sizeof(t_diff));
for(int i=1;i<=n*(n-1)/2;i++)
{
cin>>s1>>s2>>s3;
init();
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>s1;
rank[num[s1]] = m-i+1;
}
for(int i=1;i<=n;i++) lst[i] = i;
sort(lst+1, lst+n+1, sco);
memset(vis, 0, sizeof(vis));
int l = 1;
while(l < n)
{
int p = l;
while(p+1<=n && sco(lst[l], lst[p+1])==0) p++;
if(p > l) gao(l, p);
l = p+1;
}
for(int i=1;i<=n;i++)
cout<<name[lst[i]]<<endl;
}
return 0;
}
}}}题意：一个小组有n支队伍，两两之间进行一场球赛，现在知道每场的结果和排名规则，求最后的排名
规则英文写的好坑啊。。到最后才发现题意理解错了-_-##
规则按优先顺序：
s) 首先按照分数排序，每场赢者得3分，平则各一分
a) 按照平分的队伍集合中两两之间的比赛获得的分数排序
b) 按这个集合中比赛获得的净胜球的累积排序。。不是最大一场净胜球。。-_-###
c) 按这个集合中比赛的进球数排序
d) 对于tie的情况反复应用abc直到没作用
e) 按总净胜球的累积排序。。不是最大一场净胜球。。-_-###
f) 按总进球数排序
g) 按一个ranklist排序
解法：递归排序即可。。
#include <iostream>
#include <map>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
const int MAXN = 505;
map<string, int> num;
bool vis[MAXN][MAXN];
string s1, s2, s3;
int n, m, score[MAXN], diff[MAXN][MAXN], goal[MAXN][MAXN], rank[MAXN];
int lst[MAXN], pts[MAXN][MAXN], e_diff[MAXN], e_goal[MAXN], e_pts[MAXN];
int t_goal[MAXN], t_diff[MAXN], tot;
string name[MAXN];
int get_n(string& s)
{
if(num[s] == 0)
{
num[s] = ++tot;
name[tot] = s;
}
return num[s];
}
void init()
{
int a = get_n(s1),
b = get_n(s3),
ga, gb;
for(int i=0;i<s2.size();i++)
if(s2[i] == ':')
s2[i] = ' ';
istringstream in(s2);
in>>ga>>gb;
if(ga > gb)
{
pts[a][b] = 3;
pts[b][a] = 0;
}
if(gb > ga)
{
pts[b][a] = 3;
pts[a][b] = 0;
}
if(ga == gb)
pts[a][b] = pts[b][a] = 1;
score[a] += pts[a][b];
score[b] += pts[b][a];
goal[a][b] = ga;
goal[b][a] = gb;
diff[a][b] = ga-gb;
diff[b][a] = gb-ga;
t_goal[a] += ga;
t_goal[b] += gb;
t_diff[a] += diff[a][b];
t_diff[b] += diff[b][a];
}
bool abc(int a, int b)
{
if(e_pts[a] != e_pts[b]) return e_pts[a] > e_pts[b];
if(e_diff[a] != e_diff[b]) return e_diff[a] > e_diff[b];
return e_goal[a] > e_goal[b];
}
bool efg(int a, int b)
{
if(t_diff[a] != t_diff[b]) return t_diff[a] > t_diff[b];
if(t_goal[a] != t_goal[b]) return t_goal[a] > t_goal[b];
return rank[a] > rank[b];
}
bool sco(int a, int b)
{
return score[a] > score[b];
}
void gao(int l, int r)
{
if(vis[l][r])
{
sort(lst+l, lst+r+1, efg);
return;
}
vis[l][r] = 1;
for(int i=l;i<=r;i++)
{
int a = lst[i];
e_pts[a] = e_diff[a] = e_goal[a] = 0;
}
for(int i=l;i<=r;i++)
for(int j=l;j<=r;j++)
{
int a = lst[i], b = lst[j];
if(a != b)
{
e_pts[a] += pts[a][b];
e_diff[a] += diff[a][b];
e_goal[a] += goal[a][b];
}
}
sort(lst+l, lst+r+1, abc);
while(l < r)
{
int p = l;
while(p+1<=r && abc(lst[l], lst[p+1])==0) p++;
if(p > l) gao(l, p);
l = p+1;
}
}
int main()
{
int cs = 0;
while(cin>>n)
{
if(cs++) cout<<endl;
num.clear();
tot = 0;
memset(score, 0, sizeof(score));
memset(t_goal, 0, sizeof(t_goal));
memset(t_diff, 0, sizeof(t_diff));
for(int i=1;i<=n*(n-1)/2;i++)
{
cin>>s1>>s2>>s3;
init();
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>s1;
rank[num[s1]] = m-i+1;
}
for(int i=1;i<=n;i++) lst[i] = i;
sort(lst+1, lst+n+1, sco);
memset(vis, 0, sizeof(vis));
int l = 1;
while(l < n)
{
int p = l;
while(p+1<=n && sco(lst[l], lst[p+1])==0) p++;
if(p > l) gao(l, p);
l = p+1;
}
for(int i=1;i<=n;i++)
cout<<name[lst[i]]<<endl;
}
return 0;
}