期末考试
信息提取: 学生有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)
