Portkey

T1

得不了分的签到题 我觉得不显然的贪心

1.1

子任务是各种A巨大，B巨小之类的 看起来就贪了

1.2

注意到答案是单峰的： 修改出成绩时间会减少同学不愉快度，增加老师不愉快度 $\Delta v=(AorB)-C$是定值 所以单峰

处理单峰函数，使用三分 考虑挪动还是加人，贪心去优的 注意有可能无法挪动

总$O(n\log n)$

1.3

移就是塞

using namespace std; #define in Read() typedef long long ll; ll in{ ll i=0ll;bool f=true;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f^=1; while(isdigit(ch)) i=(i<<1ll)+(i<<3ll)+ch-48ll,ch=getchar(); return f?i:-i; } const int N=1e5+5; int A,B,C,n,m,tot; int p[N],t[N],maxx,minn=0x3f3f3f3f; int del,col,use[N]; ll ans,nw; // t for students // p for publisher int main(){ // system("fc 1.out 2.out"); // return 0; // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); scanf("%d%d%d%d%d",&A,&B,&C,&n,&m); // printf("%d %d %lld\n",A,B,C); if(A>B) A=B; for(int i=1;i<=n;++i) ++t[in]; for(int i=1,a;i<=m;++i){ ++p[a=in]; if(a>maxx) maxx=a; if(a<minn) minn=a; } for(int i=1;i<maxx;++i) if(t[i]){ ans+=1ll*C*(maxx-i)*t[i]; tot+=t[i]; } while(true){ col=maxx,nw=ans; while(col==maxx&&minn+1<maxx){ del=min(p[minn],p[maxx]); p[minn]-=del; p[minn+1]+=del; p[maxx]-=del; p[maxx-1]+=del; use[minn+1]+=del; ans+=1ll*A*del; if(!p[minn]) ++minn; if(!p[maxx]) --maxx; } while(col==maxx){ if(use[maxx]){ p[maxx]-=use[maxx]; p[maxx-1]+=use[maxx]; ans+=1ll*use[maxx]*(B-A); use[maxx]=0; if(!p[maxx]) --maxx; }else{ p[maxx-1]+=p[maxx]; ans+=1ll*B*p[maxx]; p[maxx]=0; --maxx; } } ans-=1ll*tot*C; if(ans>=nw){ ans=nw; break; } tot-=t[maxx]; // cout<<ans<<endl; } printf("%lld\n",ans); return 0; }