3516 - 不服sala

小明是一只活蹦乱跳的小学生。和所有小学生一样，他十分喜欢玩《英雄联盟》，并且经常和他的好朋友小涛一起玩。小明最擅长的英雄是诺克萨斯之手——也就是论坛中外号“小学生之手”的一位英雄（作为小学生，他就会蛮易信这类= =你懂的），而小涛会的英雄有很多，小明每次和小涛sala（solo，单挑，1v1，反正就是这个意思）的时候都会落到下风。

某天，小明终于急眼了，决定和小涛来一场生死<span>sala</span><span>！</span><span>1</span><span>局</span><span>200QB</span><span>！小明用英雄联盟盒子查询了自己和小涛会的英雄的战斗力，决定好好的排兵布阵，来压制小涛的嚣张气焰。</span>

假设他们每个人都会<span>m</span><span>个英雄，每个英雄的战斗力是固定的，战斗力高的英雄必定能够战胜战斗力低的英雄（比如小明虽然只会诺克萨斯之手，但是他诺手的战斗力有</span><span>10000</span><span>，打小涛战斗力</span><span>9999</span><span>的剑圣也能每次都获胜），战斗力相同的话算平局，双方都不用给</span><span>Q</span><span>币。&nbsp;&nbsp;&nbsp;&nbsp;小明因为比较弱，可以自由的指定自己英雄的出场顺序和小涛英雄的出场顺序（怎么感觉像某战国时期的故事呢），小涛不能拒绝。双方每个英雄都只能出场</span><span>1</span><span>次，且必须出场。</span>

现在问题来了，在小明选取最优策略的情况下，他最多可以赚小涛多少<span>QB</span><span>呢？要是小明无论如何都赢不了小涛，那么输出小涛能赢小明多少</span><span>QB</span><span>。</span>

<img src="http://tk.hustoj.com:80/attached/image/20141211/20141211135039_53121.png" alt="" />

Input

第一行T，输入的组数。

对每一组数据，第一行m，为他们会的英雄的个数（1<m<10），之后的一行有m个数据(题目保证m小于100)，代表小明会的m个英雄的战斗力。接下来的1行也有m个数据，代表小涛会的m个英雄的战斗力。

Output

对每组输入的数据，在单独的一行中输出。

如果小明在选择最优对阵情况下可以从小涛那里获得Q币，比如小明有三个英雄，战斗力1000,2000,3000，小涛有三个英雄战斗力1500,2500,3500，小明的最优策略是用1000对3500（输200），3000vs2500（赢200），2000vs1500（赢200），总共获得200QB，那么输出”Xiaoming will get 200QB”，如果双方打平的话输出”Xiaoming will get 0QB”

如果小明采用最优策略也无法赢小涛Q币，比如小明两个英雄战斗力1000,1000，小涛战斗力18000,20000，两局都会输，那小明怎么努力也打不过小涛（青铜五用战术打最强王者是没用的），净输400QB，那么输出”Xiaotao will get 400QB”。

Examples

Input

4
3
9200 8300 7100
9500 8700 7400
2
2000 2000
2000 2000
2
2000 1900
2200 1800
2
1800 1700
1900 2000

Output

Xiaoming will get 200QB
Xiaoming will get 0QB
Xiaoming will get 0QB
Xiaotao will get 400QB

Solution C++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;

int tian[1001];
int qi[1001];

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int horse,n;
    //ifstream cin;
    //ofstream cout;
    //cin.open("d.in");
    //cout.open("d.out");
    cin>>n;
    while(n--)
    {
        cin>>horse;
        int tianbest,tianworst,qibest,qiworst;
        int counter=0;
        if(horse==0)
            break;
        for(int i=0;i<horse;i++)
            cin>>tian[i];
        for(int j=0;j<horse;j++)
            cin>>qi[j];
        sort(tian,tian+horse,cmp);
        sort(qi,qi+horse,cmp);
        tianbest=0;
        qibest=0;
        tianworst=horse-1;
        qiworst=horse-1;
        int dui=0;
        while(dui++<horse)
        {
            if(tian[tianbest]>qi[qibest])
            {
                counter+=200;
                tianbest++;
                qibest++;
            }

            else if(tian[tianbest]<qi[qibest])
            {
                counter-=200;
                tianworst--;
                qibest++;
            }

            else if(tian[tianbest]==qi[qibest])
            {
                if(tian[tianworst]>qi[qiworst])
                {
                    counter+=200;
                    tianworst--;
                    qiworst--;
                }
                else
                {
                    if(tian[tianworst]<qi[qibest])
                    {
                        counter-=200;
                    }

                       tianworst--;
                       qibest++;
                }
            }




        }
        if(counter>=0)
        {
            cout<<"Xiaoming will get "<<counter<<"QB"<<endl;
        }
        else
        {
            cout<<"Xiaotao will get "<<-counter<<"QB"<<endl;
        }
        //cout<<counter<<endl;

    }
    return 0;
}

Time Limit	2 seconds
Memory Limit	128 MB

Discuss Stats

上一题下一题