2018美团codeM

 4.分数

题目描述:小胖参加了人生中最重要的比赛——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个整数w1, w2, ..., wn，表示每场比赛的权重，第i场比赛的权重为wi/(w1+w2+...+wn)，保证wi >= 0且1 <= w1 + w2 + ... + wn <= 1000。接下来n行每行m个整数，第i个整数表示这个选手在第i场比赛中获得的成绩。如果这个数字为-1表示这个数据丢失，保证恰好有一个-1。输出描述:n行每行输出一个1到3之间的整数。1表示一定出线，2表示一定不出线，3表示可能出线。

输入描述:第一行四个正整数n,m,k,C (m <= 6, k <= n <= 500, C <= 500)。接下来一行m个整数w1, w2, ..., wn，表示每场比赛的权重，第i场比赛的权重为wi/(w1+w2+...+wn)，保证wi >= 0且1 <= w1 + w2 + ... + wn <= 1000。接下来n行每行m个整数，第i个整数表示这个选手在第i场比赛中获得的成绩。如果这个数字为-1表示这个数据丢失，保证恰好有一个-1。

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

示例1:

2

上述输入分别对应A B C D四个人，当B第二轮成绩从0-200变化时，成绩加权平均，利用MATLAB 绘图看看在这之间的变化

假设除缺失值外最大的值是max,故只需判断0以及[max,C] (C大于等于max) ，若max大于C ,则只判断0和C 即可。

int main() {
	int n, m, k, C;
	int loseRow = -1;//丢失的下标 第loseRow位选手
	int loseCol = -1;//丢失的下标 第loseCol轮成绩

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

	/*数组取大一个值使得下标从1开始*/
	int **score = new int*[n + 1];
	for (int i = 0; i <= n; i++) {
		score[i] = new int[m + 1];
	}
	int *weight = new int[m + 1];
	float *weightScore = new float[n + 1];
	float *weightScoreTemp = new float[n + 1];
	int *promotions = new int[n + 1];//是否晋级 1,2,3
	int *promotionsTemp = new int[n + 1];
	int *max = new int[m + 1];//保存每轮最大值
	for (int i = 1; i <= m; i++) {
		cin >> weight[i];
		if (weight[i] < 0) {
			return -1;
		}
	}
	for (int i = 1; i <= n; i++) {
		promotions[i] = 2;
		promotionsTemp[i] = 2;//初始化为2
		for (int j = 1; j <= m; j++) {
			cin >> score[i][j];
			if (score[i][j] == -1) {
				if (loseRow != -1) {
					return -1;
				}
				loseRow = i;
				loseCol = j;
				score[i][j] = 0;
			}
		}
	}
	for (int j = 1; j <= m; j++) {
		max[j] = 0;
		for (int i = 1; i <= n; i++) {
			if (score[i][j] > max[j]) {
				max[j] = score[i][j];
			}
		}
	}
        //计算缺失值为0时，每个人的是否会晋级保存在promotions中  
	computePromotions(score, weightScoreTemp, weightScore, promotions, max, weight, n, m, k);
	int minValue = max[loseCol] > C ? C : max[loseCol];
	for (int loseValue = minValue; loseValue <= C; loseValue++) {
		if (loseValue > max[loseCol]) {
			max[loseCol] = loseValue;
		}
		score[loseRow][loseCol] = loseValue;
		//计算此种情况的每个人的是否会晋级保存在promotionsTemp中
		computePromotions(score, weightScoreTemp, weightScore, promotionsTemp, max, weight, n, m, k);
		for (int i = 1; i <= n; i++) {
			if (promotions[i] ^ promotionsTemp[i]) {
				promotions[i] = 3;
			}
			promotionsTemp[i] = 2;//初始化
		}

	}
	for (int i = 1; i <= n; i++) {
		cout << promotions[i] << endl;
	}
	delete[] max;
	delete[] promotions;
	delete[] promotionsTemp;
	delete[] weightScoreTemp;
	delete[] weightScore;
	delete[] weight;
	for (int i = 0; i <= n; i++) {
		delete[] score[i];
	}
	delete[] score;
	return 0;
}