暴力模拟题：分数-蒲公英云

暴力模拟题：分数

向右看齐 2023-10-06 08:51 107阅读 0赞

暴力模拟题：分数

题目：

在这里插入图片描述

思路：

应在long long表示的数据范围内解决问题，因此不应以除法进行权重计算，将计算权重的公式进行转换，左右两侧同时乘以每轮最大分数的乘积，将除法转换为乘法

由于-1可为0~C中的任意数，每个值都对应一种不同的情况，遍历所有情况，用c1,c2记录每个参赛者出现一定晋级、一定淘汰的次数

在遍历-1取值的过程中，计算每个参赛者的总得分，设为t，创建总得分的副本为s，对总得分的副本按降序排序，若t[i]>=s[k-1]，则i一定晋级，c1[i]++；若t[i]<=s[k]，则i一定淘汰，c2[i]++。

在遍历完成后，按参赛者顺序，根据c1、c2输出结果。若c2[i]==0，则在所有情况中，都未被淘汰，因此必定晋级，输出1；若c1[i]==0，则在所有情况中，都未晋级，因此必定淘汰，输出2；否则输出3

代码：

#include<vector>
#include<algorithm>
#include<iostream>
#include<string.h> 
using namespace std;
const int maxm = 6;
typedef long long ll;
const int N = 500;
bool cmp( ll x, ll y ) {
    return x > y;
}
ll sx, sy, n, m, k, C;
ll s[N], t[N], sw[maxm], w[maxm], a[N][maxm], sm[maxm], c1[N], c2[N];
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];                    //w为比赛权重 
    }
    for( ll i = 0; i < n; i ++ ) {
        for( ll j = 0; j < m; j ++ ) {
            cin >> a[i][j];                //a存储分数 
            if( a[i][j] == -1 ) {
                sx = i, sy = j;            //记录-1出现的位置 
            }
        }
    }
    for( ll c = 0; c <= C; c ++ ) {
        a[sx][sy] = c;                    //可为0~C之间的数 
        for( ll i = 0; i < m; i ++ ) {
            sm[i] = 0;                    //sm为每轮最大分数 
            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];                //sw为每轮的权重 
            if( sm[i] == 0 ) {
                //若最大分为0，该轮权重为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;
}