新手做啥网站好,网站开发人员兼职,青岛优化网站诊断,大型网站建设建设公司排名Unfair contest
题意#xff1a;
两个人参赛#xff0c;n个评委打分#xff0c;去掉s个最高分#xff0c;去掉t个最低分#xff0c;剩下分求平均分#xff0c;平均分大的获胜。你是第n个评委#xff0c;此时已知前n-1个评委所打分数#xff0c;现在轮到你打分#x…Unfair contest
题意
两个人参赛n个评委打分去掉s个最高分去掉t个最低分剩下分求平均分平均分大的获胜。你是第n个评委此时已知前n-1个评委所打分数现在轮到你打分要求你在保证第一个人获胜的情况下使得a-b最小(a为你给第一个人打的分数b为你给第二个人打的分数)
题解
我和队友是这样想的 目前已经有n-1对分数已经确定此时要去掉s个最高分t个最低分那我们将最高的s-1个分数舍弃最低的t-1个舍去因为无论第n个人怎么取分都必然要舍去。好现在问题就成了剩下成绩中要去掉一个最高分一个最低分然后问第n个人如何打分 因为第n个人不知道他打分如何他的打分决定了到底哪个最大值和最小值被舍弃有可能是第n个的成绩被舍弃也有可能是之前成绩的最高分被舍弃因此需要我们去分类讨论 九种情况对于第一个人三种情况第二个人三种情况三种分别是c在s后c在st之间c在t后我们简称第n个人的评分为c之前n-1个成绩的最高分和最低分分别是s和t
对于第一个人cs,对于第二个人cs此时去掉最高分t去掉最低分c(对于两个人都是)对于第一个人cs对于第二个人ct对于第一个人cs对于第二个人sct对于第一个人sct对于第二个人cs对于第一个人sct对于第二个人sct对于第一个人sct对于第二个人ct对于第一个人ct对于第二个人cs对于第一个人ct对于第二个人sct对于第一个人ct对于第二个人ct 我们先把蓝色部分统计好然后分九种情况依次去判断是否符合要求记录最大差值一定不重不漏。 分类讨论每种情况下的最大差值很麻烦我和队友一点点分析才写完。 但是一直wa因为我们忘了特判s0t0的各种情况如果s0t0说明不用去掉最大最小值此时最左侧和最右侧时c的取值情况在完成初始化后依旧判断。初始化0和n1的情况因为这是c的取值 a[0]1;a[n1]h;b[0]1;b[n1]h; 我也说不上明白我们这个方法很麻烦但是能做出来详细看看代码理解
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn1e510;
const int inf0x3f3f3f3f;
ll T,s,t,h,n;
ll a[maxn];
ll b[maxn];
int main()
{//freopen(input.txt,r,stdin); //freopen(output.txt,w,stdout); cinT;while(T--){cinnsth;swap(s,t);int flag0;ll ansinf;for(int i1;in-1;i)scanf(%d,a[i]);for(int i1;in-1;i)scanf(%d,b[i]);sort(a1,an);sort(b1,bn);ll upqd0;ll dwqd0;n--;a[0]1;a[n1]h;b[0]1;b[n1]h; for(int is1;in-t;i){upqda[i];dwqdb[i];}ll tupqdupqd;ll tdwqddwqd;//1 s stupqdupqda[s];tdwqddwqdb[s];if(tupqdtdwqd){flag1;ansmin(ans,1-b[s]);}//2 s ttupqdupqda[s];tdwqddwqdb[n-t1];if(tupqdtdwqd){flag1;ansmin(ans,1-h);}//coutflagendl;//3 s ctupqdupqda[s];tdwqddwqd;//couttupqd tdwqdendl;//coutflagendl;if(tupqdtdwqdb[s]){flag1;ll tmpmin(tupqd-tdwqd-1,b[n-t1]);ansmin(ans,1-(tmp));//}//4 c s//coutflagendl;tupqdupqd;tdwqddwqdb[s];if(tupqda[n-t1]tdwqd){flag1;ll tmpmax(tdwqd-tupqd1,a[s]);ansmin(ans,tmp-b[s]);}//5 c c//coutansendl;tupqdupqd;tdwqddwqd;if(tupqda[n-t1]tdwqdb[s]){flag1;ll tmpmax((tdwqd-tupqd)1,a[s]-b[n-t1]);ansmin(ans,tmp);}//6 c ttupqdupqd;tdwqddwqdb[n-t1];if(tupqda[n-t1]tdwqd){flag1;ll tmpmax(a[s],tdwqd-tupqd1);ansmin(ans,tmp-h);}//7 t stupqdupqda[n-t1];tdwqddwqdb[s];if(tupqdtdwqd){flag1;ansmin(ans,a[n-t1]-b[s]);}//8 t ctupqdupqda[n-t1];tdwqddwqd;if(tupqdtdwqdb[s]){flag1;ll tmpmin((tupqd-tdwqd-1),b[n-t1]);ansmin(ans,a[n-t1]-tmp);}//9 t ttupqdupqda[n-t1];tdwqddwqdb[n-t1];if(tupqdtdwqd){flag1;ansmin(ans,a[n-t1]-h);}if(flag)coutansendl;else coutIMPOSSIBLEendl;}return 0;
}
