当前位置: 代码迷 >> 综合 >> 【SHOISXOI2017】bzoj4868 期末考试
  详细解决方案

【SHOISXOI2017】bzoj4868 期末考试

热度:7   发布时间:2024-01-13 10:47:18.0

枚举最后一门考试的结束时间,用前缀和、后缀和统计需要更改的总时间和费用。
好像可以用三分做?

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=100000;
int s1[maxn+10],s2[maxn+10],sp[maxn+10],cnt[maxn+10],n,m,l,r;
LL w1[maxn+10],w2[maxn+10],wp[maxn+10],a,b,c,now,ans;
void solve0()
{int p;for (int i=1;;i++)if (sp[i]){p=i;break;}if (w1[p]>=w2[p]) printf("%lld\n",a*w2[p]);else printf("%lld\n",a*w1[p]+b*(w2[p]-w1[p]));
}
int main()
{freopen("exam.in","r",stdin);freopen("exam.out","w",stdout);int x;scanf("%lld%lld%lld%d%d",&a,&b,&c,&n,&m);a=min(a,b);for (int i=1;i<=n;i++){scanf("%d",&x);sp[x]++;r=max(r,x);}for (int i=1;i<=m;i++){scanf("%d",&x);cnt[x]++;r=max(r,x);}for (int i=1;i<=r;i++){sp[i]+=sp[i-1];s1[i]=s1[i-1]+cnt[i];wp[i]=wp[i-1]+sp[i-1];w1[i]=w1[i-1]+s1[i-1];}for (int i=r;i;i--){s2[i]=s2[i+1]+cnt[i];w2[i]=w2[i+1]+s2[i+1];}if (c>1e12){solve0();return 0;}ans=1e15;for (int i=1;i<=r;i++){now=c*wp[i];if (w1[i]>=w2[i]) now+=a*w2[i];else now+=a*w1[i]+b*(w2[i]-w1[i]);ans=min(ans,now);}printf("%lld\n",ans);fclose(stdout);
}