[文章目录]
Description
Alice和Bob在玩一个游戏，每一轮Bob都会给Alice两个整数A和B(1<=A,B<=100)，Alice每一轮必须把目前所有的A序列和B序列中的数一一配对，每个数必须用且只使用一次，要求最大和最小。
贪心+模拟。经证明发现答案只相当于每次将其中一个序列从大到小排序，另一个序列从小到大排序，然后相同位置的数相加，找最大的那个就是答案。
然后，发现排序时间不够。而数字为100以内正整数，所以，搞一个数组记录出现次数再摸拟排序的过程就可以得出结论了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n,cnt;
int numa[110],numb[110];
int find()
{
int sw,re=-1;
int posa=0,posb=0;
int a=0,b=101;
while(posa<=cnt&&posb<=cnt)
{
if(numa[a]==0) sw=0;
else if(numb[b]==0) sw=1;
else
{
re=max(re,a+b);
if(numa[a]+posa>numb[b]+posb) sw=2;
else if(numa[a]+posa<numb[b]+posb) sw=3;
else sw=4;
}
switch(sw)
{
case 0:a++;break;
case 1:b--;break;
case 2:posb+=numb[b];b--;break;
case 3:posa+=numa[a];a++;break;
case 4:posa+=numa[a];a++;posb+=numb[b];b--;break;
}
}
return re;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int x,y;
scanf("%d%d",&x,&y);
numa[x]++,numb[y]++,cnt++;
printf("%d\n",find());
}
return 0;
}