AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 2795. 期末考试    原题链接    困难

作者: 作者的头像   墨红鱼 ,  2024-08-04 21:22:00 ,  所有人可见 ,  阅读 4


0



#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;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息