美团2018年CodeM大赛-资格赛 分数 暴力模拟
2024-09-02 00:27:46
链接：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）。
小胖想知道对于每个人的出线情况是怎么样的，也就是一定能出线，一定不能出线还是有可能出线。
比如说，资格赛一共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
输出
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;
}
最新文章
- Nancy之实现API的功能
- VS2010编译Boost 1.57 静态链接库
- 2016年5月面试题(Unity&iOS)
- Windows 2012 R2图标以及字体颜色发生变化更改成默认设置
- 处理海量数据的高级排序之——堆排序（C++）
- WinForm 弹框确认后执行
- spring集成quartz scheduler
- Nagios监控部署(转)
- leetcode problem 42 -- Trapping Rain Water
- oracle_11g 不同用户之间的数据迁移
- C#泛型类的简单创建与使用
- python下 help()使用方法
- Mysql优化之创建高性能索引(二)
- [Python]网络爬虫（四）：Opener与Handler的介绍和实例应用
- LeetCode(55)- Palindrome Linked List
- [Swift]LeetCode448. 找到所有数组中消失的数字 | Find All Numbers Disappeared in an Array
- Maven pom详解
- RecyclerView联动滑动失败
- Java基础中的RMI介绍与使用
- 关于各种BUF源语的研究