Description 有n位同學，每位同學都參加了全部的m門課程的期末考試，都在焦急的等待成績的公佈。第i位同學希望在第ti天 或之前得知所.有.課程的成績。如果在第ti天，有至少一門課程的成績沒有公佈，他就會等待最後公佈成績的課程 公佈成績，每等待一天就會產生C不愉快度。對於第i門課程，按照原本 ...
Submit: 936 Solved: 426
[Submit][Status][Discuss]
Description
有n位同學，每位同學都參加了全部的m門課程的期末考試，都在焦急的等待成績的公佈。第i位同學希望在第ti天 或之前得知所.有.課程的成績。如果在第ti天，有至少一門課程的成績沒有公佈，他就會等待最後公佈成績的課程 公佈成績，每等待一天就會產生C不愉快度。對於第i門課程，按照原本的計劃，會在第bi天公佈成績。有如下兩種 操作可以調整公佈成績的時間：1.將負責課程X的部分老師調整到課程Y，調整之後公佈課程X成績的時間推遲一天 ，公佈課程Y成績的時間提前一天；每次操作產生A不愉快度。2.增加一部分老師負責學科Z，這將導致學科Z的出成 績時間提前一天；每次操作產生B不愉快度。上面兩種操作中的參數X,Y,Z均可任意指定，每種操作均可以執行多次 ，每次執行時都可以重新指定參數。現在希望你通過合理的操作，使得最後總的不愉快度之和最小，輸出最小的不 愉快度之和即可Input
第一行三個非負整數A,B,C，描述三種不愉快度，詳見【問題描述】； 第二行兩個正整數n,m(1≤n,m≤105)，分別表示學生的數量和課程的數量； 第三行n個正整數ti，表示每個學生希望的公佈成績的時間； 第四行m個正整數bi，表示按照原本的計劃，每門課程公佈成績的時間。 1<=N,M,Ti,Bi<=100000,0<=A,B,C<=100000Output
輸出一行一個整數，表示最小的不愉快度之和。Sample Input
100 100 24 5
5 1 2 3
1 1 2 3 3
Sample Output
6由於調整操作產生的不愉快度太大，所以在本例中最好的方案是不進行調整; 全部
5 的門課程中，最慢的在第 3 天出成績;
同學 1 希望在第 5 天或之前出成績，所以不會產生不愉快度;
同學 2 希望在第 1 天或之前出成績，產生的不愉快度為 (3 - 1) * 2 = 4;
同學 3 希望在第 2 天或之前出成績，產生的不愉快度為 (3 - 2) * 2 = 2;
同學 4 希望在第 3 天或之前出成績，所以不會產生不愉快度;
不愉快度之和為 4 + 2 = 6 。
HINT
存在幾組數據，使得C = 10 ^ 16
Source
考場上還是靜不下心來
總感覺這題是個dp
然後直接棄掉了。
其實還是挺簡單的。
我們欽定一個試卷被批完的最晚時間
然後通過二分+首碼和計算出學生的不愉快度
再利用二分+尾碼和計算出讓最後一個被批完的試卷的時間滿足要求的不愉快的
兩者求和取最小值就可以了
這道題的關鍵是看出學生不滿意度和試卷被批完的時間之間的單調關係
然後要想到枚舉時間
#include<cstdio> #include<cmath> #include<algorithm> #define int unsigned long long using namespace std; const int MAXN=1e5+10; const int INF=1e19; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int A,B,C; int N,M; int t[MAXN],b[MAXN]; int sumt[MAXN],sumb[MAXN];//t的首碼與b的尾碼 int limit,ans=INF; main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif 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(),limit=max(limit,b[i]); sort(t+1,t+N+1); sort(b+1,b+M+1); for(int i=1;i<=N;i++) sumt[i]=t[i]+sumt[i-1]; for(int i=M;i>=1;i--) sumb[i]=b[i]+sumb[i+1]; for(int i=1;i<=limit;i++) { int l=1,r=N,ans1=0,ans2=0,now=0; while(l<=r) { int mid=l+r>>1; if(t[mid]<i) ans1=mid,l=mid+1; else r=mid-1; } l=1,r=M; while(l<=r) { int mid=l+r>>1; if(b[mid]>i) ans2=mid,r=mid-1; else l=mid+1; } if(ans1!=0) now+=(ans1*i-sumt[ans1])*C; if(ans2!=0) { int need=(sumb[ans2]-(M-ans2+1)*i); if(A>=B) now+=need*B; else { int have=(ans2-1)*i-(sumb[1]-sumb[ans2]); if(have>=need) now+=need*A; else now+=have*A+(need-have)*B; } } ans=min(ans,now); } printf("%lld",ans); return 0; }
