美团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

>= 0且1 <= w

+ w

+ ... + w

<= 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;
}