4868: [Shoi2017]期末考试

题解：

　　 Get到一个新姿势...三分法

　　一开始百度百科的时候下了一跳...中国...的根？？？

　　学懂了之后其实运用起来就根二分差不多啊，不过证明...不是很懂%大佬
　　先喷一波自己：没看到最小值...一直维护的是一个上凸包ORZ

　　然后知道了三分，计算答案的时候就直接用贪心嘛（比较一下那种不愉快度小就尽量用那种，统计一下当前解一共提前了和延后了多少天），不过因为没有操作可以单独推迟，所以少了一种情况。

　　再打一波脸：存在几组数据，使得C = 10 ^ 16（大视野写的真大）有这句话，longlong都爆了啊...加特判ORZ

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 LL A,B,C;

 LL n,m;

 LL a[],b[];

 LL sol(LL x)

 {

     LL sum=;

     if(A<B)

     {

         LL s1=,s2=;//表示需要推迟的总天数 和 提前的总天数

         for(int i=;i<=m;i++)if(b[i]<x)s1+=(x-b[i]);

         for(int i=;i<=m;i++)if(b[i]>x)s2+=(b[i]-x);

         if(s1>=s2)sum+=(s2*A);//用操作1直接解决

         else sum+=(s1*A+(s2-s1)*B);//操作1+操作2

     }

     else for(int i=;i<=m;i++)if(b[i]>x)sum+=(b[i]-x)*B;//因为没有操作是单独推迟的，所以少了一种情况

     for(int i=;i<=n;i++)if(a[i]<x)sum+=(x-a[i])*C;

     return sum;

 }

 int main()

 {

     scanf("%lld%lld%lld",&A,&B,&C);

     scanf("%lld%lld",&n,&m);

     for(int i=;i<=n;i++)scanf("%lld",&a[i]);

     for(int i=;i<=m;i++)scanf("%lld",&b[i]);

     LL l=,r=1e5,mid,mmid;

     LL ans1,ans2,ans3,ans4;

     ans1=ans2=ans2=ans4=;

     if(C==1e16)

     {

       LL mmin=1e18;

       for(int i=;i<=n;i++)mmin=min(mmin,a[i]);

       printf("%lld\n",sol(mmin));

       return ;

     }

     while(l+<r)

     {

         mid=(l+r)/,mmid=(mid+r)/;

         ans1=sol(mid),ans2=sol(mmid);

         if(ans1==ans2)l=mid,r=mmid;

         else if(ans1<ans2)r=mmid;

         else l=mid;

     }

     mid=(l+r)/,mmid=(mid+r)/;

     ans1=sol(l),ans2=sol(r),ans3=sol(mid),ans4=sol(mmid);

     printf("%lld\n",min(min(ans1,ans2),min(ans3,ans4)));

     return ;

 }

三分

bzoj4868: [Shoi2017]期末考试（三分法）

4868: [Shoi2017]期末考试