洛谷 P3745 [六省联考2017]期末考试

题目描述

有

第 $tit_iti 天或之前得知所有课程的成绩。如果在第 tit_iti 天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生 CCC 不愉快度。$

对于第 $bib_ibi 天公布成绩。$

有如下两种操作可以调整公布成绩的时间:

将负责课程
增加一部分老师负责学科

上面两种操作中的参数

现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。

输入输出格式

输入格式：

第一行三个非负整数 $tit_iti，表示每个学生希望的公布成绩的时间；第四行 mmm 个正整数 bib_ibi，表示按照原本的计划，每门课程公布成绩的时间。$

输出格式：

输出一行一个整数，表示最小的不愉快度之和。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

输入样例#2： 复制

3 5 4
5 6
1 1 4 7 8
2 3 3 1 8 2

输出样例#2： 复制

说明

【样例 1 说明】

由于调整操作产生的不愉快度太大，所以在本例中最好的方案是不进行调整; 全部

5 的门课程中，最慢的在第 3 天出成绩;

同学 1 希望在第 5 天或之前出成绩，所以不会产生不愉快度;

同学 2 希望在第 1 天或之前出成绩，产生的不愉快度为 (3 − 1) ∗ 2 = 4;

同学 3 希望在第 2 天或之前出成绩，产生的不愉快度为 (3 − 2) ∗ 2 = 2;

同学 4 希望在第 3 天或之前出成绩，所以不会产生不愉快度;

不愉快度之和为 4 + 2 = 6 。

题解:

　　　不知道为什么,最近总是做贪心题,这个题目,我们发现序列的答案只和最后一门公布答案的学科的时间有关,于是我们枚举最后一门学科公布的时间x,强制让所有的学科在这一天之前前公布,统计前面学科可以救助他们的次数和要让所有科目都在x之前的最小操作次数,比较A和B,尽量用小的就可以了.

　　不知道为什么必须开unsigned long long,不然会wa两个点.

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 200010
#define ll unsigned long long
using namespace std;
ll A,B,C;
ll a[MAXN],b[MAXN],suma[MAXN],sumb[MAXN];
ll n,m,maxx,ans=1ll<<60;

int erfen(ll s[],int l,int r,int now){
    int ans=0,mid;
    while(l<=r){
        int mid=(l+r)/2;
        if(s[mid]<=now) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

ll work(int now){
    ll sav=0,cos=0,ps;
    ps=erfen(b,1,m,now);
    sav=ps*now-sumb[ps],cos=(sumb[m]-sumb[ps])-(m-ps)*now;
    ll ex=0,bs=0;
    ps=erfen(a,1,n,now);
    bs=max((now*ps-suma[ps])*C,(ll)0);
    if(A>=B) ex=cos*B;
    else{
        if(sav>=cos) ex=cos*A;
        else ex=sav*A+(cos-sav)*B;
    }
    return bs+ex;
}

int main()
{
    cin>>A>>B>>C;cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++) scanf("%lld",&b[i]),maxx=max(maxx,b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(int i=1;i<=n;i++) suma[i]=suma[i-1]+a[i];
    for(int i=1;i<=m;i++) sumb[i]=sumb[i-1]+b[i];
    for(int i=1;i<=maxx;i++) ans=min(ans,work(i));
    printf("%lld",ans);
    return 0;
}