CF 204B Little Elephant and Cards
题目链接: 传送门
Little Elephant and Cards
time limit per test:2 second memory limit per test:256 megabytes
Description
The Little Elephant loves to play with color cards.
He has n cards, each has exactly two colors (the color of the front side and the color of the back side). Initially, all the cards lay on the table with the front side up. In one move the Little Elephant can turn any card to the other side. The Little Elephant thinks that a set of cards on the table is funny if at least half of the cards have the same color (for each card the color of the upper side is considered).
Help the Little Elephant to find the minimum number of moves needed to make the set of n cards funny.
Input
The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of the cards. The following n lines contain the description of all cards, one card per line. The cards are described by a pair of positive integers not exceeding 10^9 — colors of both sides. The first number in a line is the color of the front of the card, the second one — of the back. The color of the front of the card may coincide with the color of the back of the card.
The numbers in the lines are separated by single spaces.
Output
On a single line print a single integer — the sought minimum number of moves. If it is impossible to make the set funny, print -1.
Sample Input
3
4 7
4 7
7 4
5
4 7
7 4
2 11
9 7
1 1
Sample Output
0
2
解题思路:
题目大意:有N张牌,每张牌正反两面都有颜色,问最少要翻转几次才能才能使一半的卡有相同的颜色。
感觉是STL的应用,选好map来找键值,set来创建集合,题目就很简单了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef __int64 LL;
int main()
{
int N;
while (~scanf("%d",&N))
{
LL x,y;
map<LL,LL>m1,m2;
map<LL,LL>::iterator itt;
set<LL>s;
set<LL>::iterator it;
for (int i = 0;i < N;i++)
{
scanf("%I64d%I64d",&x,&y);
m1[x]++;
if (x != y)
{
m2[y]++;
}
s.insert(x);
s.insert(y);
}
LL res = INF;
LL tmp = (N+1)/2;
for (it = s.begin();it != s.end();it++)
{
x = *it;
if (m1[x] + m2[x] >= tmp)
{
res = min(res,max(0LL,tmp - m1[x]));
}
}
if(res == INF)
{
res = -1;
}
printf("%I64d\n",res);
}
return 0;
}
最新文章
- jBPM4.4 no jBPM DB schema: no JBPM4_EXECUTION table. Run the create.jbpm.schema target first in the install tool.
- 如何用java自带的工具生成证书
- 20161127-emmagee
- Session一次错误记录
- windows下安装redis和memcached
- PBOC APDU命令解析【转】
- ubuntu 以root 运行程序
- Delphi XE5 for android 使用 BITMAP STYLE DESIGNER 改变控件背景
- IOS中实现图片点击全屏预览
- Fast CGI 工作原理
- Android_按钮被按下效果的实现(selector选择器)
- MTK Android Driver:GPIO
- JS开发调试
- web计时机制——performance对象
- 201521123032 《Java程序设计》第4周学习总结
- CentOS7 nginx安装
- 性能测试进阶指南——基础篇之磁盘IO
- 【BZOJ2823】[AHOI2012]信号塔(最小圆覆盖)
- Codeforces550C(SummerTrainingDay01-H)
- 用UIInterpolatingMotionEffect产生透视效果