net网络网站建设,建设教育协会官网,广州私人做网站,北京本地网络推广平台解析
其实并不简单的一道题。
是刘汝佳老师的例题#xff0c;搜到之后按照讲的策略写了一发。 #xff08;由于这个策略并不完全正确#xff0c;就不展开讲了#xff09; 好啊#xff01; 可是感觉讲的策略特别对#xff0c;为什么呢#xff1f;
原因在于#xff0…解析
其实并不简单的一道题。
是刘汝佳老师的例题搜到之后按照讲的策略写了一发。 由于这个策略并不完全正确就不展开讲了 好啊 可是感觉讲的策略特别对为什么呢
原因在于课上的策略是建立于 比赛非赢即输的前提下而本题存在平局。 当最小值相等时这个贪心直接让最小值去找最大值送死或者让两个最小值打平都不一定是最优的。 分别的hack数据
5
1 1 7 9 10
1 3 5 6 9 3
6 7 9
6 8 10以下设 a1...na_{1...n}a1...n 是田忌的马b1...nb_{1...n}b1...n 是齐王的马按升序排列x−yx-yx−y 表示 x,yx,yx,y 对局 那么怎么办呢 注意到我们可以用类似的套路对最大值进行处理那么我们现在的问题就只在于如何处理最大值和最小值都相等的时候了即 a1b1,anbna_1b_1,a_nb_na1b1,anbn。 在 a1b1anbna_1b_1a_nb_na1b1anbn 的时候怎么选结果都是一样的因此我们只讨论 a1an,b1bna_1a_n,b_1b_na1an,b1bn 的情况。
一个朴素的想法还是用最小值霍霍对方的最大值 (a1−bna_1-b_na1−bn)而此时这个做法是对的以下给出证明。 假设最优解并非如此就有a1−bj,ai−bna_1-b_j,a_i-b_na1−bj,ai−bn此时的价值优于 a1−bn,ai−bja_1-b_n,a_i-b_ja1−bn,ai−bj 接下来分情况讨论
aibja_ib_jaibj两种决策的价值都是-400换成 a1,bna_1,b_na1,bn 不会变劣。aibja_ib_jaibj右边的价值是-200而左边的价值为-200或-400换成 a1,bna_1,b_na1,bn 不会变劣。aibja_ib_jaibj右边的价值是0而左边的两场比赛一场我方是最小值一场对方是最大值都赢不了换成 a1,bna_1,b_na1,bn 不会变劣。
综上所述使 a1−bna_1-b_na1−bn 始终是不劣的。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e6100;
const int M1e6100;
const int mod1e9;
int n;
int a[N],b[N],pl,ans;signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();for(int i1;in;i) a[i]read();for(int i1;in;i) b[i]read();sort(a1,a1n);sort(b1,b1n);int al1,arn,bl1,brn;while(alar){if(a[al]b[bl]){al;--br;ans-200;}else if(a[al]b[bl]){al;bl;ans200;}else if(a[ar]b[br]){--ar;--br;ans200;}else if(a[ar]b[br]){al;--br;ans-200;}else{if(a[al]b[br]) ans-200;al;--br;}}printf(%d\n,ans);return 0;
}
/*
3
2 2 2
2 2 3
*/
