Game of Credit Cards
After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards.
Rules of this game are simple: each player bring his favourite n-digit credit card. Then both players name the digits written on their cards one by one. If two digits are not equal, then the player, whose digit is smaller gets a flick (knock in the forehead usually made with a forefinger) from the other player. For example, if n = 3, Sherlock's card is 123 and Moriarty's card has number 321, first Sherlock names 1 and Moriarty names 3 so Sherlock gets a flick. Then they both digit 2 so no one gets a flick. Finally, Sherlock names 3, while Moriarty names 1 and gets a flick.
Of course, Sherlock will play honestly naming digits one by one in the order they are given, while Moriary, as a true villain, plans to cheat. He is going to name his digits in some other order (however, he is not going to change the overall number of occurences of each digit). For example, in case above Moriarty could name 1, 2, 3 and get no flicks at all, or he can name 2, 3 and 1 to give Sherlock two flicks.
Your goal is to find out the minimum possible number of flicks Moriarty will get (no one likes flicks) and the maximum possible number of flicks Sherlock can get from Moriarty. Note, that these two goals are different and the optimal result may be obtained by using different strategies.
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of digits in the cards Sherlock and Moriarty are going to use.
The second line contains n digits — Sherlock's credit card number.
The third line contains n digits — Moriarty's credit card number.
First print the minimum possible number of flicks Moriarty will get. Then print the maximum possible number of flicks that Sherlock can get from Moriarty.
3
123
321
0
2
2
88
00
2
0
First sample is elaborated in the problem statement. In the second sample, there is no way Moriarty can avoid getting two flicks.
刚开始以为是说田忌赛马福尔摩斯版,实际上有一点不一样,读题很重要。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <xfunctional>
#define ll long long
#define mod 998244353
using namespace std;
int dir[][] = { {,},{,-},{-,},{,} };
const int maxn = 1e5 + ;
const long long inf = 0x7f7f7f7f7f7f7f7f; int main()
{
int n, sf = , mf = ;
cin >> n;
string s, m;
cin >> s;
cin >> m;
vector<int> sn, mn;
for (int i = ; i < s.size(); i++)
{
sn.push_back(s[i] - '');
mn.push_back(m[i] - '');
}
sort(mn.begin(), mn.end());
for (int i = ; i < s.size(); i++)
{
vector<int>::iterator iter;
iter = lower_bound(mn.begin(), mn.end(), sn[i]);
if (iter == mn.end())
{
sf++;
}
else
mn.erase(iter);
}
mn.clear();
for (int i = ; i < s.size(); i++)
{
mn.push_back(m[i] - '');
}
sort(mn.begin(), mn.end());
for (int i = ; i < s.size(); i++)
{
vector<int>::iterator iter;
iter = upper_bound(mn.begin(), mn.end(), sn[i]);
if (iter != mn.end())
{
mn.erase(iter);
mf++;
}
}
cout << sf << endl;
cout << mf << endl;
return ;
}
最新文章
- chattr用法
- CSS:CSS使用Tips
- HTTP 错误 404.2 - Not Found 由于 Web 服务器上的“ISAPI 和 CGI 限制”列表设置,无法提供您请求的页面
- spring expression
- Open vSwitch流表应用实战
- 【leetcode】Contains Duplicate &; Rectangle Area(easy)
- HDU 4638 Group ★(树状数组)
- vi/vim正则表达式
- 【转】图文并茂 Ubuntu使用Thunderbird方法指南
- layerX offsetX pageX
- 【转】使用Boost Graph library(二)
- Ghostscript.Net Pdf 转 Image
- Java设计模式-模板模式
- 【bzoj 1095】[ZJOI2007]Hide 捉迷藏
- framework7 入门(数据获取和传递)
- 【Java】「深入理解Java虚拟机」学习笔记(2)- JVM内存区域
- ansible创建vmware虚拟机
- [ACM] poj 2017 Speed Limit
- bzoj1375 双调路径
- Bootstrap中关于input里file的样式更改
热门文章
- mysql 数据库中存在重复记录,删除保留其中一条
- PAT (Basic Level) Practice (中文)1070 结绳 (25 分) (优先队列)
- 堆之*bin理解
- mysql空数据的处理
- 2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛 Banana
- Linux安装U盘启动报错Failed to load ldlinux.c32
- java - GC垃圾收集器详解(三)
- WSO2 ESB XML定义语法(1)
- PHP返回json数据为null
- linux - python2.6.6 升级到python2.7.14