期末考试

链接

信息提取: 学生有n名,他们要考m个科目,每个人都有希望所有成绩出分的天数

这里给出的学生的不满意度C,只要出分成绩晚了k天,学生就会产生k x C的不满意度

题目还给出两种调整出分方式

1.将X科目的老师调到Y科目,X延迟出分一天,Y提前一天,产生A点老师不满意度

2.增加老师到Z科目,Z科目提前一天,产生B点老师不满意度

我们需要做的,就是找到最佳调整方式,是总不满意度最小

首先,我们不妨思考,最佳调整方式是调整什么

应该是最晚所有科目的出分天数

假设最晚所有出分科目的天数为T,那么T的范围应在学生希望出分天数的值域内

设总不满意度为f(T),应该能想到f(T)是先减后增的,就可以使用三分法解决(当然,如果某些数据特别离谱,就成了一直递减(老师的不满意度非常大)或一直递增(学生的不满意度非常大),照样能用三分法解决)

还有一个问题,我们怎么计算f(T)

如果A>=B的话,我们只只需要采用第二种调整方式进行了

如果A<B的话,我们先尽可能得采用第一种调整方式,在采用第二种调整方式

当然,还要考虑最特殊的情况,也就是C=10^16,此时如果还用函数判断就不行了

推测原因是数字太大,超过了long long的最大范围

这个情况我们只需要将T调整为左边界就行了,因为学生的不满意度是天文数字,太大了

代码实现

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long f(int T, vector<int>&b, vector<int>&t,long long A,long long B,long long C) {
	
	long long neg = 0, finals = 0;
	long long teacher_cost = 0;
	if (A < B) {
		for (int i = 0;i < b.size();i++) {
			if (b[i] < T) {
				neg += (b[i] - T);
			}
			else {
				finals += (b[i] - T);
			}
		}
		if (finals + neg > 0) {
			teacher_cost = B * (finals + neg) + (-neg) * A;
		}
		else {
			teacher_cost = A * finals;
		}
	
	}
	else {
		for (int i = 0;i < b.size();i++) {
			teacher_cost += B * (b[i] > T ?  b[i]-T : 0);
		}
	}
	long long student_cost = 0;
	for (int i = 0;i < t.size();i++) {
		student_cost += C * (t[i] < T ? T - t[i] : 0);
	}
	return student_cost + teacher_cost;
}
int main() {
	long long A, B, C;
	cin >> A >> B >> C;
	int m, n;
	cin >> n >> m;
	vector<int>t(n), b(m);
	for (int i = 0;i < n;i++) {
		cin >> t[i];
	}
	for (int i = 0;i < m;i++) {
		cin >> b[i];
	}
	int right = *max_element(t.begin(), t.end()), left = *min_element(t.begin(), t.end());
	if (C > 1e15) {
		cout << f(left, b, t, A, B, C);
		return 0;
	}
	/*cout << f(1, b, t, A, B, C) << endl;*/
	long long min_cost = 0;
	while (left <= right) {
		int mid_l = left - (left - right) / 3, mid_r = right - (right - left) / 3;
		long long l_cost = f(mid_l, b, t, A, B, C), r_cost = f(mid_r, b, t, A, B, C);
		if (l_cost > r_cost) {
			left = mid_l + 1;
			min_cost = r_cost;
			/*cout <<"r_cost" << r_cost << endl;*/
		}
		else {
			right = mid_r - 1;
			min_cost = l_cost;
			/*cout <<"l_cost" << l_cost << endl;
			cout <<"right" << right << endl;*/
		}
	}
	cout << min_cost;
}

注释是我的调试,不用看

时间复杂度:O((n+m)logR) R为数据范围,即right-left

空间复杂度:O(n+m)