首页 > 代码库 > [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]期末考试(贪心)