先叠甲,这不是题解。
我看到贪心做法都是双指针,自己想的是用 multiset 做。
先用田忌的马比赛齐王的马中第一个比这匹马小的马。
然后田忌用相等的马与齐王剩下的马中相等的马平局。
剩下的比赛就是必输了。
这种贪心好想而且好写。
关键代码
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
multiset<int>msa,msb;
for(int i=1;i<=n;i++)msa.insert(a[i]),msb.insert(b[i]);
auto it=msa.begin();
while(it!=msa.end())
{
auto pos=msb.lower_bound(*it);
if(pos==msb.begin())
{
it=next(it);
}
else
{
pos=prev(pos);
it=msa.erase(it);
msb.erase(pos);
ans+=200;
}
}
for(auto c:msa)
{
auto pos=msb.lower_bound(c);
if(pos==msb.end()||*pos!=c)continue;
msb.erase(pos);
}
ans-=msb.size()*200;
cout<<ans;
}