期末考试

整数三分

#include<bits/stdc++.h>
const int N = 10;
using namespace std;
typedef long long ll;
int n,m,t[N],b[N];                                    //学生n与课程m的数量
ll A,B,C,ans;                                         // A,B,C的不愉快度
ll calc1(int p){                                      //计算通过A，B操作把时间调到p的不愉快度
  ll x=0,y=0; 
  for(int i=1;i<=m;i++){                              //课程数量遍历
    if(b[i]<p) x += p-b[i];                           //加上可以被推迟的天数
    else y += b[i]-p;                                 //加上需要被提前的天数
  }
  if(A<B) return min(x,y)*A+(y-min(x,y))*B;           //A<B,先用A填补，再用B
  // min(x,y) == x → xA-xB+yB (A<B) A解决一部分后用B min(x,y) == y → yA 全部可以用A解决
  else return y*B;                                    //B<=A,直接全部使用B
}
ll calc2(int p) {                                     //计算学生们的不愉快度总和
  ll sum=0;
  for(int i=1;i<=n;i++)                               //遍历学生期望数组
    if(t[i]<p) sum += (p-t[i])*C;                     //超过预期时间累计不愉快*c
  return sum;
}
int main(){
  cin>>A>>B>>C>>n>>m;                                 // A,B,C的不愉快度和学生n与课程m的数量
  for(int i=1;i<=n;i++) cin >> t[i];                  //学生期望数组
  for(int i=1;i<=m;i++) cin >> b[i];                  //成绩公布数组
  sort(b+1,b+m+1); sort(t+1,t+n+1);                   //数组排序
  if(C>=1e16) { cout<<calc1(t[1])<<endl; return 0;}   //一个特判
  ans=1e16;
  int l=1,r=N; //left, right
  while(r-l > 2){                                     //把2改成其他数字也行，后面的for再找最小值
    int mid1 = l+(r-l)/3; int mid2 = r-(r-l)/3;       //三等分
    ll c1 = calc1(mid1) + calc2(mid1); /              //总不愉快度
    ll c2 = calc1(mid2) + calc2(mid2);
    if (c1<=c2) r = mid2;
    else l = mid1;
  }
  for(int i=l;i<=r;i++){ //在上面求出的区间内再枚举时间求出最小值
    ll x = calc1(i) + calc2(i);
    ans = min(ans,x);
  }
  cout<<ans<<endl;
  return 0;
}

笔记：学生的不愉快度只与最晚公布成绩的时间有关。总不愉快度呈下凸图像，所以我们三分这个最晚公布成绩的时间，尝试通过AB操作计算将时间调整所产生的不愉快度，再加上学生的总不愉快度（C）,不断逼近极值即可。注意C极大时要特判，因为C极大，选AB调整肯定更优。