Unfair contest

題意：

兩個(gè)人參賽，n個(gè)評(píng)委打分，去掉s個(gè)最高分，去掉t個(gè)最低分，剩下分求平均分，平均分大的獲勝。你是第n個(gè)評(píng)委，此時(shí)已知前n-1個(gè)評(píng)委所打分?jǐn)?shù)，現(xiàn)在輪到你打分，要求你在保證第一個(gè)人獲勝的情況下，使得a-b最小(a為你給第一個(gè)人打的分?jǐn)?shù)，b為你給第二個(gè)人打的分?jǐn)?shù))

題解：

我和隊(duì)友是這樣想的：
目前已經(jīng)有n-1對(duì)分?jǐn)?shù)已經(jīng)確定，此時(shí)要去掉s個(gè)最高分，t個(gè)最低分，那我們將最高的s-1個(gè)分?jǐn)?shù)舍棄，最低的t-1個(gè)舍去，因?yàn)闊o(wú)論第n個(gè)人怎么取分，都必然要舍去。好，現(xiàn)在問(wèn)題就成了，剩下成績(jī)中要去掉一個(gè)最高分，一個(gè)最低分，然后問(wèn)第n個(gè)人如何打分？
因?yàn)榈趎個(gè)人不知道他打分如何？他的打分決定了到底哪個(gè)最大值和最小值被舍棄，有可能是第n個(gè)的成績(jī)被舍棄，也有可能是之前成績(jī)的最高分被舍棄，因此需要我們?nèi)シ诸?lèi)討論
九種情況（對(duì)于第一個(gè)人三種情況，第二個(gè)人三種情況），三種分別是：c在s后，c在st之間，c在t后，我們簡(jiǎn)稱(chēng)第n個(gè)人的評(píng)分為c，之前n-1個(gè)成績(jī)的最高分和最低分分別是s和t

對(duì)于第一個(gè)人c<s,對(duì)于第二個(gè)人c<s，此時(shí)去掉最高分t，去掉最低分c(對(duì)于兩個(gè)人都是)

對(duì)于第一個(gè)人c<s，對(duì)于第二個(gè)人c>t

對(duì)于第一個(gè)人c<s，對(duì)于第二個(gè)人s<c<t

對(duì)于第一個(gè)人s<c<t，對(duì)于第二個(gè)人c<s

對(duì)于第一個(gè)人s<c<t，對(duì)于第二個(gè)人s<c<t

對(duì)于第一個(gè)人s<c<t，對(duì)于第二個(gè)人c>t

對(duì)于第一個(gè)人c>t，對(duì)于第二個(gè)人c<s

對(duì)于第一個(gè)人c>t，對(duì)于第二個(gè)人s<c<t

對(duì)于第一個(gè)人c>t，對(duì)于第二個(gè)人c>t

我們先把藍(lán)色部分統(tǒng)計(jì)好，然后分九種情況依次去判斷是否符合要求，記錄最大差值，一定不重不漏。
分類(lèi)討論每種情況下的最大差值，很麻煩，我和隊(duì)友一點(diǎn)點(diǎn)分析才寫(xiě)完。
但是一直wa，因?yàn)槲覀兺颂嘏衧=0，t=0的各種情況，如果s=0，t=0，說(shuō)明不用去掉最大最小值，此時(shí)最左側(cè)和最右側(cè)時(shí)c的取值情況，在完成初始化后，依舊判斷。初始化0和n+1的情況，因?yàn)檫@是c的取值

a[0]=1;a[n+1]=h;b[0]=1;b[n+1]=h;

我也說(shuō)不上明白，我們這個(gè)方法很麻煩，但是能做出來(lái)，詳細(xì)看看代碼理解

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const int inf=0x3f3f3f3f; ll T,s,t,h,n; ll a[maxn]; ll b[maxn]; int main() {//freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin>>T;while(T--){cin>>n>>s>>t>>h;swap(s,t);int flag=0;ll ans=inf;for(int i=1;i<=n-1;i++)scanf("%d",&a[i]);for(int i=1;i<=n-1;i++)scanf("%d",&b[i]);sort(a+1,a+n);sort(b+1,b+n);ll upqd=0;ll dwqd=0;n--;a[0]=1;a[n+1]=h;b[0]=1;b[n+1]=h; for(int i=s+1;i<=n-t;i++){upqd+=a[i];dwqd+=b[i];}ll tupqd=upqd;ll tdwqd=dwqd;//1 s stupqd=upqd+a[s];tdwqd=dwqd+b[s];if(tupqd>tdwqd){flag=1;ans=min(ans,1-b[s]);}//2 s ttupqd=upqd+a[s];tdwqd=dwqd+b[n-t+1];if(tupqd>tdwqd){flag=1;ans=min(ans,1-h);}//cout<<flag<<endl;//3 s ctupqd=upqd+a[s];tdwqd=dwqd;//cout<<tupqd<<" "<<tdwqd<<endl;//cout<<flag<<endl;if(tupqd>tdwqd+b[s]){flag=1;ll tmp=min(tupqd-tdwqd-1,b[n-t+1]);ans=min(ans,1-(tmp));//}//4 c s//cout<<flag<<endl;tupqd=upqd;tdwqd=dwqd+b[s];if(tupqd+a[n-t+1]>tdwqd){flag=1;ll tmp=max(tdwqd-tupqd+1,a[s]);ans=min(ans,tmp-b[s]);}//5 c c//cout<<ans<<endl;tupqd=upqd;tdwqd=dwqd;if(tupqd+a[n-t+1]>tdwqd+b[s]){flag=1;ll tmp=max((tdwqd-tupqd)+1,a[s]-b[n-t+1]);ans=min(ans,tmp);}//6 c ttupqd=upqd;tdwqd=dwqd+b[n-t+1];if(tupqd+a[n-t+1]>tdwqd){flag=1;ll tmp=max(a[s],tdwqd-tupqd+1);ans=min(ans,tmp-h);}//7 t stupqd=upqd+a[n-t+1];tdwqd=dwqd+b[s];if(tupqd>tdwqd){flag=1;ans=min(ans,a[n-t+1]-b[s]);}//8 t ctupqd=upqd+a[n-t+1];tdwqd=dwqd;if(tupqd>tdwqd+b[s]){flag=1;ll tmp=min((tupqd-tdwqd-1),b[n-t+1]);ans=min(ans,a[n-t+1]-tmp);}//9 t ttupqd=upqd+a[n-t+1];tdwqd=dwqd+b[n-t+1];if(tupqd>tdwqd){flag=1;ans=min(ans,a[n-t+1]-h);}if(flag)cout<<ans<<endl;else cout<<"IMPOSSIBLE"<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Unfair contest(个人做法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。