题目链接
题目思路
经过观察可以发现
对于两个序列 其中下标 t+1 到 n-s是一定会被选择的
那么还差 （n-s-t ） - （n-s-t+1）=1个待选
这个选择为三种 可能是 t 可能是n-s+1 也可能是 你作为裁判给出的那个数字
然后对于两位选手的序列选择
有这么 3*3 =9种选择
我的代码是直接判断九种情况 如果有一种符合题意就flag=1 然后取最小的ans
详情见代码
其中我把s和t swap了
#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()
{cin>>T;while(T--){scanf("%lld%lld%lld%lld",&n,&s,&t,&h);//cin>>n>>s>>t>>h;int flag=0;ll ans=inf;for(int i=1;i<=n-1;i++)scanf("%lld",&a[i]);for(int i=1;i<=n-1;i++)scanf("%lld",&b[i]);sort(a+1,a+n);sort(b+1,b+n);ll upqd=0;ll dwqd=0;n--;swap(s,t);for(int i=s+1;i<=n-t;i++){upqd+=a[i];//上面数组的已确定答案 dwqd+=b[i];}a[0]=1;//注意初始化 这样可以保证s=0或t=0时候结果正确 a[n+1]=h;b[0]=1;b[n+1]=h;//s代表选择前面的哪个可选 t代表选择后面的那个可选//1 s s 第一个选手选择s 第二个选手选择s tupqd=upqd+a[s];tdwqd=dwqd+b[s];if(tupqd>tdwqd)//是否符题意 让黑幕成功 {flag=1;ans=min(ans,1-b[s]);}//2 s t 第一个选手选择s 第二个选手选择n-t+1 tupqd=upqd+a[s];tdwqd=dwqd+b[n-t+1];if(tupqd>tdwqd){flag=1;ans=min(ans,1-h);}//3 s c 第一个选手选择s 第二个选手选择c 裁判数 tupqd=upqd+a[s];tdwqd=dwqd;if(tupqd>tdwqd+b[s]){flag=1;ll tmp=min(tupqd-tdwqd-1,b[n-t+1]);//对于第二个c直接等于二者差 但是不能大于b[n-t+1]否则取不到c ans=min(ans,1-(tmp));//第一个c等于1 这样满足ans最小 }//4 c s tupqd=upqd;tdwqd=dwqd+b[s];if(tupqd+a[n-t+1]>tdwqd){flag=1;ll tmp=max(tdwqd-tupqd+1,a[s]);//对于第一个c直接等于二者差 但是不能小于a[s]否则取不到c ans=min(ans,tmp-b[s]);}//5 c ctupqd=upqd;tdwqd=dwqd;if(tupqd+a[n-t+1]>tdwqd+b[s]){flag=1;//答案直接等于二者差 同时不能小于a[s]-b[n-t+1] 否则c取不到 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;
}官方题解
特判后
直接输出差值
差值一定包含那些 一定会被选择的差值
而且当 aL>=bL 时刻 差值还会包含 一部分
这一部分是a【s】-1 的差值
当aR>=bR时刻同理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll a[maxn],b[maxn],h;
int _,n,s,t;
int main(){//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);scanf("%d",&_);while (_--){scanf("%d%d%d%lld",&n,&s,&t,&h); n--;assert(s+t<=n);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);for (int i=1;i<=n;i++) scanf("%lld",&b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);a[0]=b[0]=1; a[n+1]=b[n+1]=h;ll sa=0,sb=1;for (int i=t+1;i<=n-s;i++) sa+=a[i],sb+=b[i];ll aL=sa+a[t],aR=sa+a[n-s+1];ll bL=sb+b[t],bR=sb+b[n-s+1];if (aR<bL) puts("IMPOSSIBLE");else if (aL>=bR){printf("%lld\n",1-h);} else {ll r=0;if (aL>=bL) r=max(r,a[t]-1);if (aR>=bR) r=max(r,h-b[n-s+1]);printf("%lld\n",sb-sa-r);} }return 0;
}