首页 > 代码库 > [BZOJ 4868][SHOI&SXOI2017]期末考试（贪心）
[BZOJ 4868][SHOI&SXOI2017]期末考试（贪心）
Description
有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天
或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程
公布成绩，每等待一天就会产生C不愉快度。对于第i门课程，按照原本的计划，会在第bi天公布成绩。有如下两种
操作可以调整公布成绩的时间：1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天
，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。2.增加一部分老师负责学科Z，这将导致学科Z的出成
绩时间提前一天；每次操作产生B不愉快度。上面两种操作中的参数X,Y,Z均可任意指定，每种操作均可以执行多次
，每次执行时都可以重新指定参数。现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不
愉快度之和即可
Solution
考试的时候并没有想到QAQ
正解应该是三分啦…但是直接枚举Deadline线性可做
具体实现见代码
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#define MAXN 100005#define INF 1e16typedef long long LL;using namespace std;int n,m,a,b,c;LL student[MAXN],course[MAXN];int read(){ int x=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c=getchar(); while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar(); return x;}int main(){ a=read(),b=read(),c=read(),n=read(),m=read(); int day=0;LL cost=0,mov=0,left=0,ans; for(int i=1;i<=n;i++) {int t;t=read();student[t]++;day=max(day,t);} for(int i=1;i<=m;i++) {int t;t=read();course[t]++;day=max(day,t);} for(int i=1;i<=day;i++) { cost+=student[i]*(day-i); left+=course[i]*(day-i); student[i]+=student[i-1];//维护前缀和 course[i]+=course[i-1]; } ans=cost*c; for(int i=day-1;i>0;i--) { mov+=(m-course[i]);//在这天后完结的课需要向前移动一天 left-=course[i];//前面的所有课程向后移动的范围减少了1天 cost-=student[i];//减掉希望在这天以前完结的学生一天的不满意度 if(c>=INF&&cost)continue; LL p=left>0?left:0; if(mov<p)p=mov; if(a<b)ans=min(ans,p*a+(mov-p)*b+cost*c); else ans=min(ans,mov*b+cost*c); } printf("%lld\n",ans); return 0;}
[BZOJ 4868][SHOI&SXOI2017]期末考试（贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。