AcWing 2795. 期末考试
原题链接
困难
作者:
墨红鱼
,
2024-08-04 21:22:00
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int A, B, C;
int t[N], b[N],n,m;
int cal1(int p) {//计算最后公布成绩时间为p时,调整老师所需要的不愉快度
int need = 0;//需要往前调整的时间
int rest = 0;//可以为方案1调整提供的时间
for (int i = 1; i <= m; i++)
if (b[i] > p)need += b[i]-p ;//需要往前调整
else rest += p-b[i] ;//可以提供调整时间
if (A > B)return need * B;//第2方案不愉快度更小,全部选择第2方案
else {
if (need > rest)return rest * A + (need - rest) * B;//判断rest是否能提供need所需
else return need * A;
}
}
int cal2(int p) {//计算最后公布成绩时间为p时,学生的不愉快度
int sum = 0;
for (int i = 1; i <= n; i++)
if (t[i] < p) sum += (p - t[i]) * C;
return sum;
}
signed main() {
scanf("%lld%lld%lld", &A, &B,&C);
scanf("%lld%lld", &n, &m);
int MAX = 0;//学生最大期待
for (int i = 1; i <= n; i++)scanf("%lld",&t[i]),MAX=max(t[i],MAX);
for (int i = 1; i <= m; i++)scanf("%lld", &b[i]);
//sort(b + 1, b + 1 + m);
sort(t + 1, t + 1 + n);//学生期待升序排序
//特判学生不愉快度C太大,只能满足所有学生的期待
if (C == 1e16) {cout << cal1(t[1]); return 0;}
int l = 0, r = MAX;//左右边界
while (r - l > 2) {
int t = (r - l) / 3;
int mid1 = l + t, mid2 = r - t;
if (cal1(mid1) + cal2(mid1) < cal1(mid2) + cal2(mid2))r = mid2;
else l = mid1;
}
int MIN = LLONG_MAX;//统计最后公布成绩时间在区间[l,r]中最小不愉快值
for (int i = l; i <= r; i++)MIN = min(MIN, cal1(i) + cal2(i));
cout << MIN;
return 0;
}