BZOJ4868: [Shoi2017]期末考试

BZOJ4868

我的做法好像有点奇葩。。用的二分。 说一下自己的思路。 先将数组 t 和b排序，记 mn=t1 , mx=bm 。 分别表示最早的想知道成绩的时间，和最晚的发布成绩的时间。 那么调整发布成绩的最晚时间只会在 mn 到 mx 之间。 如果 mx<=mn 直接输出0. 假如确定了发布成绩的最晚时间 t 。 那么Ans=调整发布成绩的最晚时间到t的代价 想知道成绩的最晚天数大于t的人数∗C 这两部分都可以在 logn 时间内求出。 具体求法： 先找到 b 数组中大于等于t的第一个位子 pos ，令 ss=∑pos−1i=1t−bi ， s=∑mi=posbi−t 。这两部分记了数组 b 的前缀和都可以O(1)求了。如果 B<=A ，那么一定用 B 更优，因为A还会使某些值变大，这时第一部分答案 Ans1=B∗s 。 另外情况下，如果 ss>=s 那么全部都可以用 A 不会使前面小的值大于t，此时 Ans1=A∗s 。如果 ss<s ，那么能用 A 的用A，剩下的用 B ，此时Ans1=A∗ss B∗(s−ss) 第二部分就好求了。二分找到 t 中大于等于t的第一个位置。。记录个前缀和就可求了。。

这个方法无法过掉全部数据。（ C 只有三个取值范围<=1e2, <=1e5 <script type="math/tex" id="MathJax-Element-15883"><=1e5</script>, 1e16 ）当 C=1e16 时，第二部分答案会爆掉 long long 。 发现当 C=1e16 时， A,B<=1e5 ，那这时显然 t=mn 时答案不会超过 1e15 。特判一下就可以了。

【代码】

#include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> #include <complex> #include <algorithm> #include <cmath> #define N 100005 #define INF 0x7fffffff #define mod 1000000007 using namespace std; const double pi=acos(-1); typedef long long ll; ll read() { ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } int A,B,n,m,mn=N,mx=0,id; int t[N],b[N]; ll sum[N],Sum[N],ans=1e18,C; int Find(int Del) { int l=1,r=m,rtn=1; while(l<=r) { int mid=l+r>>1; if(b[mid]>=Del) rtn=mid,r=mid-1; else l=mid+1; } return rtn; } int Findf(int Del) { int l=1,r=n,rtn=1; while(l<=r) { int mid=l+r>>1; if(t[mid]<=Del) rtn=mid,l=mid+1; else r=mid-1; } return rtn; } void Deal(int Mxb) { int pos=Find(Mxb);ll tmp=0,Tmp=0; ll s=Sum[m]-Sum[pos-1]-1LL*(m-pos+1)*Mxb; ll ss=1LL*(pos-1)*Mxb-Sum[pos-1]; if(B<=A) tmp=1LL*B*s; else if(ss>=s) tmp=1LL*s*A; else tmp=1LL*ss*A+1LL*(s-ss)*B; pos=Findf(Mxb); Tmp=1LL*(1LL*Mxb*(pos)-sum[pos])*C; tmp+=Tmp; ans=min(ans,tmp); } int main() { A=read(),B=read(),C=read(); n=read(),m=read(); for(int i=1;i<=n;i++) t[i]=read(); for(int i=1;i<=m;i++) b[i]=read(); sort(t+1,t+1+n);sort(b+1,b+1+m); mn=t[1];mx=b[m]; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i]; for(int i=1;i<=m;i++) Sum[i]=Sum[i-1]+b[i]; if(mx<=mn) { printf("0\n"); return 0; } if(C==1e16) { Deal(mn); printf("%lld\n",ans); return 0; } for(int i=mx;i>=mn;i--) Deal(i); printf("%lld\n",ans); return 0; }