Complex Congratulation β

Problem Description
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

题解:用贪心做;

首先将01、10立场的人按影响力从大到小一对一对加入,当01,10任意一方有多余的人时,将11立场的人和10和01中多出来的人 以及 00立场的人 按照影响力降序一对一对加入名单。是11与01(或10)还是11与00入名单取决于01(或10)和00哪一方的最高影响力更高,直到11立场的人全部入队为止。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ling long
#define INF 0×3f3f3f3f  //0×7ffffff
#define EPS 1e-6
#define maxn 600000+10
#define PI acos(-1.0)
using namespace std;
int a[maxn],b[maxn],c[maxn],d[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t,x,v;
    ll ans;
    int pop1,pop2,pop3,pop4;
    int sum1,sum2,sum3,sum4;
    while(cin>>t)
    {
        ans=0;
        pop1=pop2=pop3=pop4=0;
        sum1=sum2=sum3=sum4=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        while(t--)
        {
            cin>>x>>v;
            if(x==11) {a[pop1++]=v;sum1+=v;}//11
            if(x==1)  {b[pop2++]=v;sum2+=v;}//01
            if(x==10) {c[pop3++]=v;sum3+=v;}//10
            if(x==0)  {d[pop4++]=v;sum4+=v;}//00
        }
        sort(b,b+pop2,greater<int>());
        sort(c,c+pop3,greater<int>());
        sort(d,d+pop4,greater<int>());
        if(pop2==pop3)
        {
            ans=ans+sum2+sum3;
            if(pop1>=pop4) ans=ans+sum1+sum4;
            else
            {
                ans+=sum1;
                for(int i=0;i<pop1;i++) ans+=d[i];
            }
        }
        else if(pop2>pop3)
        {
            ans=ans+sum1+sum3;
            for(int i=0;i<pop3;i++) ans+=b[i];
            int tot=0,pos1=pop3,pos2=0;
            while(tot<pop1)
            {
                if(pos1<=pop2-1&&pos2<=pop4-1)
                {
                    if(b[pos1]>=d[pos2])
                    {
                        ans+=b[pos1];
                        tot++;pos1++;
                    }
                    else
                    {
                        ans+=d[pos2];
                        tot++;pos2++;
                    }
                }
                else if(pos1<=pop2-1&&pos2==pop4)
                {
                    ans+=b[pos1];
                    tot++;pos1++;
                }
                else if(pos1==pop2&&pos2<=pop4-1)
                {
                    ans+=d[pos2];
                    tot++;pos2++;
                }
                else if(pos1==pop2&&pos2==pop4)
                    break;
            }
        }
        else if(pop2<pop3)
        {
            ans=ans+sum1+sum2;
            for(int i=0;i<pop2;i++) ans+=c[i];
            int tot=0,pos1=pop2,pos2=0;
            while(tot<pop1)
            {
                if(pos1<=pop3-1&&pos2<=pop4-1)
                {
                    if(c[pos1]>=d[pos2])
                    {
                        ans+=c[pos1];
                        tot++;pos1++;
                    }
                    else
                    {
                        ans+=d[pos2];
                        tot++;pos2++;
                    }
                }
                else if(pos1<=pop3-1&&pos2==pop4)
                {
                    ans+=c[pos1];
                    tot++;pos1++;
                }
                else if(pos1==pop3&&pos2<=pop4-1)
                {
                    ans+=d[pos2];
                    tot++;pos2++;
                }
                else if(pos1==pop3&&pos2==pop4)
                    break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

发表评论,支持MarkDown语法