我们是冠军

时间: 1ms        内存:256M

描述:

众所周知,IG 在 S8 总决赛中拿下了……不对, 众所周知, 在今年的 ACM 省赛中,我校”伊丽莎白(xyx, zudikn, clx)”队伍力克山大拿到了冠军,ACM 赛制的比赛是非常有趣的,在这种赛制下,排名是按照以下标准执行的(如上图所示):

  1. 解题数越多越靠前
  2. 在解题数相同的情况下,罚时越少越靠前
  3. 如果某道题目未通过, 则不管提交多少次,都不计算罚时

对于罚时的定义:一道题的罚时是由两部分组成, 一部分是提交错误次数 $\times\ 20 {\rm\ min}$,另一部分是这道题目通过的时间。

例如,”伊丽莎白”队伍 E 题通过的时间是 114 min,提交 3 次通过说明前两次都错误了,则这道题他们的总罚时是 $114 + 2 \times 20 = 154 {\rm\ min}$。

现在,我们有一场比赛 $n$ 个队伍的数据, 你能帮我们计算出他们的排名吗?

输入:

输入的第一行包含两个正整数 $n, k$ $(1 \le n \le 1000, 1 \le k \le 13)$,表示共有 $n$ 支队伍,每只队伍的编号为 $1 \dots n$,该场比赛共有 $k$ 道题目。

接下来有 $n$ 行输入,其中第 $i$ 行表示第 $i$ 支队伍的数据。每一行, 有 $k$ 对数分别表示通过每道题的时间($0\le PenaltyTime \le 300$)和提交次数($0\le SubmitCount \le 500$), 如果通过的时间为 $0$ 或者提交次数为 $0$,则说明该题未通过。

我们保证不会有两支队伍排名相同。

输出:

输出只有一行为 $1\dots n$ 的一个排列, 表示这 $n$ 支队伍的排名。

示例输入:

2 3 
13 1 16 1 14 2
13 1 16 1 32 1

示例输出:

2 1

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
int main()
{
int a,b,c,d,e,f,h;
scanf("%d%d",&a,&b);
c=b*2;
int n[c],m[c];int o[a],p[a];
for(f=0;f<a;f++)
{o[f]=0; p[f]=0;}
for(e=0;e<a;e++){
for(d=0;d<c;d++){
    scanf("%d",&n[d]);


if((d+1)%2==0&&n[d]!=0&&n[d-1]!=0)
{
    p[e]=p[e]+1;
}


if((d+1)%2==0&&n[d]!=0&&n[d-1]!=0)
        o[e]=o[e]+n[d-1]+20*(n[d]-1);
   }
}

int k,g,l;
k=o[0];
g=0;
for(d=0;d<a;d++)

    if(o[d]>k)
        k=o[d];
l=k;
 for(e=0;e<a;e++)
    {  k=o[0]; g=0; for(d=0;d<a;d++)
 { if(p[d]>p[g])
 {
     g=d; k=o[d];
 }
     else if(o[d]<k&&p[d]==p[g])
 {
     k=o[d];
     g=d;
 }
 }
    p[g]=-1;printf("%d ",g+1);
    }
}


参考答案(时间最优[8]):

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;

struct node {
    int ac;
    int time;
    int id;
} a[1005];
int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        a[i].ac = a[i].time = 0;
        a[i].id = i + 1;
        for (int j = 0; j < k; j++) {
            int pen, sub;
            cin >> pen >> sub;
            if (pen == 0 || sub == 0)
                ;
            else {
                ++a[i].ac;
                a[i].time += pen + (sub - 1) * 20;
            }
        }
    }
    sort(a, a + n, [&](const node &x, const node &y) {
        if (x.ac == y.ac) {
            return x.time < y.time;
        }
        return x.ac > y.ac;
    });
    for (int i = 0; i < n; i++) {
        cout << a[i].id << " ";
    }
    cout << endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。