【贪心】【multiset】 Codeforces Round #401 (Div. 2) B. Game of Credit Cards

时间:2023-03-09 16:02:12
【贪心】【multiset】 Codeforces Round #401 (Div. 2) B. Game of Credit Cards

对第一个人的排序,然后从小到大处理,对第一个人的每枚卡片,从第二个人的卡片中选择一个大于等于它的最小的,否则选择一个当前剩下的最小的,这样可以保证负场最少。

如果选择的改成大于它的最小的,就可以保证胜场最多。

用multiset处理。

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
typedef pair<int,int> Point;
Point c[1010];
multiset<int>S,tS;
typedef multiset<int>::iterator ITER;
int n,ans;
char a[1010],b[1010],d[1010];
int main()
{
freopen("b.in","r",stdin);
scanf("%d%s%s",&n,a+1,b+1);
for(int i=1;i<=n;++i)
{
c[i].first=a[i]-'0';
c[i].second=i;
}
for(int i=1;i<=n;++i)
S.insert(b[i]-'0');
tS=S;
sort(c+1,c+n+1);
for(int i=1;i<=n;++i)
{
ITER it=S.lower_bound(c[i].first);
if(it==S.end())
{
S.erase(S.begin());
++ans;
}
else
S.erase(it);
}
printf("%d\n",ans);
ans=0;
S=tS;
for(int i=1;i<=n;++i)
{
ITER it=S.upper_bound(c[i].first);
if(it==S.end())
S.erase(S.begin());
else
{
S.erase(it);
++ans;
}
}
printf("%d\n",ans);
return 0;
}