题目描述
有 nnn 位同学，每位同学都参加了全部的 mmm 门课程的期末考试，都在焦急的等待成绩的公布。
第 iii 位同学希望在第 tit_iti 天或之前得知所有课程的成绩。如果在第 tit_iti 天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生 CCC 不愉快度。
对于第 iii 门课程，按照原本的计划，会在第 bib_ibi 天公布成绩。
有如下两种操作可以调整公布成绩的时间:
- 将负责课程 XXX 的部分老师调整到课程 YYY，调整之后公布课程 XXX 成绩的时间推迟一天，公布课程 YYY 成绩的时间提前一天；每次操作产生 AAA 不愉快度。
- 增加一部分老师负责学科 ZZZ，这将导致学科 ZZZ 的出成绩时间提前一天；每次操作产生 BBB 不愉快度。
上面两种操作中的参数 X,Y,ZX, Y, ZX,Y,Z 均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。
现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。
输入输出格式
输入格式：第一行三个非负整数 A,B,CA, B, CA,B,C，描述三种不愉快度，详见【题目描述】； 第二行两个正整数 n,mn, mn,m，分别表示学生的数量和课程的数量； 第三行 nnn 个正整数 tit_iti，表示每个学生希望的公布成绩的时间； 第四行 mmm 个正整数 bib_ibi，表示按照原本的计划，每门课程公布成绩的时间。
输出格式：输出一行一个整数，表示最小的不愉快度之和。
输入输出样例
100 100 24 55 1 2 31 1 2 3 3
6
3 5 45 61 1 4 7 82 3 3 1 8 2
33
说明
【样例 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#include #include #include #include #include #define MAXN 200010#define ll unsigned long longusing 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;}