暴力模拟题：分数

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

## 暴力模拟题：分数 ##

#### 题目： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路： ####

应在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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200516093950377.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200516094010973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70