http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&cid=832
In the world line 1.048596%
梓川咲太在解决了樱岛麻衣和丰浜和花互换身体的事件以后，又陷入到了新的麻烦里面。
......
“你们真的在交往吗？”
“是的，这是事实。”
樱岛麻衣即使有点不好意思，也依然坦诚真相。
“对方是个没神经的男生，三个月前向着全校学生向我表白。那个......”，麻衣以害羞的表情慎选言辞“我虽然一度保留，但还是被他的毅力折服了。”
记者们一连串的发问都被樱岛麻衣轻松的化解，明明是新电影发布会的现场，可是记者们对樱岛麻衣的发问却没有平息的征兆。
在一旁看着的经纪人——凉子小姐心有余悸。明星的恋爱一直是禁忌的话题，稍有差池就会断送艺人生涯。但是眼前的樱岛麻衣却能借助发布会的现场，把气氛往有利于自己的方向发展。
这自然和樱岛麻衣本身超高的交流技巧有关，还和观众有关。
“如果有话要对男朋友说，可以请您在这里说吗？”提出请求而不是询问的记者是南条文香，和梓川咲太认识，一直在追踪调查“青春期症候群”。
“不要，我要当面和他说。”樱岛麻衣难为情的笑了，那是有点害羞又有非常幸福，能烙印在灵魂深处的表情，她以这样一句话作为话题的结束。
发布会后，凉子小姐看到事情的局面发展如此顺利，想起了那天晚上樱岛麻衣小姐和她的面谈。
“对于气氛的引导”，樱岛麻衣在凉子小姐前正襟危坐“我需要过半数的记者支持我。”
“怎么界定这个支持呢？”
“记者对于明星恋爱能不能正面的报到，这个是最重要的。你的电脑里面也有关于记者的各种资料吧。拿来给我看一下。”
樱岛麻衣接过凉子小姐的电脑，熟练的打开excel，进行了一番操作以后，又把电脑给了凉子小姐。
“每个记者都有{00,10,01,11}四个数字其中的一个，还有一个数字，指的是这个记者的影响力。”
“两个观念A和B，0代表不支持，1代表支持。南条文香记者的右边是11，表示的是即支持A又支持B。而这个记者的右边是01，说明不支持A但支持B。00的话说明两个都不支持。”
“凉子小姐，你能不能帮我建立这个一个名单，人数不限，这上面的记者既有超过半数的人支持A，又有超过半数的人支持B。而且这个名单的人的总影响力最大？”
凉子小姐开始打开Visual Studio 2017。她知道这个问题只能用程序来解决，也将决定樱岛麻衣的艺人生涯。
Input
多组输入输出
第一行一个整数n，表示有n个记者（1<=n<=400000）
接下来n行，每行有两个数。
第一个数是{00,01,10,11}的其中一个，表示第i个记者的支持取向。
第二个数是ai (0<=ai<5000)，表示第i个记者的影响力。
所有测试数据的n的和不超过500000
Output
输出一个数字，表示能取得的最大的总影响力
Sample Input
5
11 1
01 1
00 100
10 1
01 1
Sample Output
103
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
using namespace std;
typedef long long ll;
const int N=100000+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
vector<int> v[4];
bool cmp(int x, int y){
return x > y;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
int n, op,m;
while(~scanf("%d", &n)){
for(int i = 0; i < 4; ++i)
v[i].clear();
ll ans = 0;
for(int i = 1; i <= n; ++i){
scanf("%d%d", &op, &m);
if(op == 11) {v[0].push_back(m);ans+=m;}
if(op == 10) v[1].push_back(m);
if(op == 1) v[2].push_back(m);
if(op == 0) v[3].push_back(m);
}
for(int i = 1; i < 3; ++i)
sort(v[i].begin(), v[i].end(), cmp);
int t1 = min(v[1].size(), v[2].size());
for(int i = 0; i < t1; ++i){
ans += v[1][i] + v[2][i];
}
for(int i = t1; i < v[1].size(); ++i)
v[3].push_back(v[1][i]);
for(int i = t1; i < v[2].size(); ++i)
v[3].push_back(v[2][i]);
sort(v[3].begin(), v[3].end(), cmp);
int num = v[0].size();
for(int i = 0; i < num && i < v[3].size(); ++i){
ans += v[3][i];
}
printf("%lld\n", ans);
}
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号