美团2018年CodeM大赛-资格赛 分数 暴力模拟

时间：2022-06-12 20:38:14

链接：https://www.nowcoder.com/acm/contest/138/D
来源：牛客网

小胖参加了人生中最重要的比赛——MedoC资格赛。MedoC的资格赛由m轮构成，使用常见的“加权标准分”的规则。每位选手需要参加所有的m轮的比赛。在一轮中，能取得的分数为自己的成绩除掉最高分的成绩。每个选手的总分为每一轮获得的分数乘上这一轮比赛占得比重。如果在某一轮比赛中所有人获得了零分，那么所有选手在这一轮获得的分数都为0分。
比如说，资格赛一共3轮，三轮的权重分别为30%, 30%, 40%。在第一轮中，小胖获得了300分，最高分也为300分。在第二轮中，小胖获得了0分，最高分也为0分。在第三轮中，小胖获得了150分，最高分为300分，那么小胖的总分为(300/300)*30%+0*30%+(150/300)*40%=0.5。
一共有n位选手参加了比赛，其中成绩最高的k位选手能够晋级到初赛。如果有多人在分数线上同分，那么系统会随机在这些同分的人中选取，选满k个晋级为止。
小胖现在知道了每个选手每场比赛的成绩，但是由于他的疏忽，其中的某个人某场比赛的成绩消失了。所以更多人出线的情况变得未知起来。现在只知道成绩一定是0到C之间的一个整数（包含0和C）。
小胖想知道对于每个人的出线情况是怎么样的，也就是一定能出线，一定不能出线还是有可能出线。

输入描述:

第一行四个正整数n,m,k,C (m <= 6, k <= n <= 500, C <= 500)。
接下来一行m个整数w

1

, w

2

, ..., w

m

，表示每场比赛的权重，第i场比赛的权重为w

i

/(w

1

+w

2

+...+w

m

)，保证w

i 

>= 0且1 <= w

1 

+ w

2 

+ ... + w

m 

<= 1000。
接下来n行每行m个整数，第i个整数表示这个选手在第i场比赛中获得的成绩。如果这个数字为-1表示这个数据丢失，保证恰好有一个-1。

输出描述:

n行每行输出一个1到3之间的整数。1表示一定出线，2表示一定不出线，3表示可能出线。

输入例子:
4 2 2 100

1 1

100 99

70 70

40 -1

100 39
输出例子:
1

3

3

2

-->

示例1

输入

复制

4 2 2 100

1 1

100 99

70 70

40 -1

100 39

输出

复制

1

3

3

2

一个大暴力模拟题，虽然很容易写，但是真的很容易出错。。。
开始直接按照题目意思模拟，结果wa到炸，后来看了别人的博客将所有牵扯到乘法的地方换成除法总算过了。
#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 1e3;

const int mod = 1e9 + 7;

typedef long long ll;

const int N = 505;

bool cmp( ll x, ll y ) {

    return x > y;

}

ll sx, sy, n, m, k, C;

ll s[maxn], t[maxn], sw[maxn], w[maxn], a[maxn][maxn], sm[maxn], c1[maxn], c2[maxn];

int main() {

    memset( c1, 0, sizeof(c1) );

    memset( c2, 0, sizeof(c2) );

    cin >> n >> m >> k >> C;

    for( ll i = 0; i < m; i ++ ) {

        cin >> w[i];

    }

    for( ll i = 0; i < n; i ++ ) {

        for( ll j = 0; j < m; j ++ ) {

            cin >> a[i][j];

            if( a[i][j] == -1 ) {

                sx = i, sy = j;

            }

        }

    }

    for( ll c = 0; c <= C; c ++ ) {

        a[sx][sy] = c;

        for( ll i = 0; i < m; i ++ ) {

            sm[i] = 0;

            for( ll j = 0; j < n; j ++ ) {

                sm[i] = max( sm[i], a[j][i] );

            }

        }

        for( ll i = 0; i < m; i ++ ) {

            sw[i] = w[i];

            if( sm[i] == 0 ) {

                sw[i] = 0;

                continue;

            }

            for( ll j = 0; j < m; j ++ ) {

                if( i != j && sm[j] != 0 ) {

                    sw[i] *= sm[j]; //将所有的除法换成乘法，仔细思考在这里除法和乘法意义相同

                }

            }

        }

        for( ll i = 0; i < n; i ++ ) {

            s[i] = 0;

            for( ll j = 0; j < m; j ++ ) {

                s[i] += a[i][j] * sw[j];

            }

            t[i] = s[i];

        }

        sort( s, s + n, cmp );

        for( ll i = 0; i < n; i ++ ) {

            if( t[i] >= s[k-1] ) {

                c1[i] ++;   //一定行的个数

            }

            if( n != k && t[i] <= s[k] ) {

                c2[i] ++;   //一定不行的个数

            }

        }

    }

    for( ll i = 0; i < n; i ++ ) {

        if( c2[i] == 0 ) {

            puts("1");

        } else if( c1[i] == 0 ) {

            puts("2");

        } else {

            puts("3");

        }

    }

    return 0;

}

　　

相关文章