题目链接

分析

很容易想到可以用DP
用f[i][j][x][y]表示已经有i个男孩&＃xff0c;j个女孩坐下来&＃xff0c;从右往前男孩最多比女孩多x个&＃xff0c;女孩最多比男孩多y个。
这道题状态转移用刷表法比较方便。

代码

#include
#include
#include
#define INF 0x7fffffff
using namespace std;
#define MAXN 100000
int n,a[MAXN&＃43;10],b[MAXN&＃43;10];
void Read(int &x){char c;while(c&＃61;getchar(),c!&＃61;EOF)if(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;){x&＃61;c-&＃39;0&＃39;;while(c&＃61;getchar(),c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;)x&＃61;x*10&＃43;c-&＃39;0&＃39;;ungetc(c,stdin);return;}
}
void read(){Read(n);int i;for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)Read(a[i]);for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)Read(b[i]);
}
int make_it_win(int *a,int *b){int i,l1,l2,r1,r2,ret&＃61;0;l1&＃61;l2&＃61;1,r1&＃61;r2&＃61;n;for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(a[r1]>b[r2])ret&＃43;&＃61;2,r1--,r2--;else if(a[l1]>b[l2])ret&＃43;&＃61;2,l1&＃43;&＃43;,l2&＃43;&＃43;;elseret&＃43;&＃61;(a[l1]&＃61;&＃61;b[r2]),l1&＃43;&＃43;,r2--;}return ret;
}
int main()
{read();sort(a&＃43;1,a&＃43;n&＃43;1);sort(b&＃43;1,b&＃43;n&＃43;1);printf("%d %d\n",make_it_win(a,b),n*2-make_it_win(b,a));
}