3516 - 不服sala

通过次数

提交次数

旧版界面

时间限制 : 2 秒内存限制 : 128 MB

小明是一只活蹦乱跳的小学生。和所有小学生一样，他十分喜欢玩《英雄联盟》，并且经常和他的好朋友小涛一起玩。小明最擅长的英雄是诺克萨斯之手——也就是论坛中外号“小学生之手”的一位英雄（作为小学生，他就会蛮易信这类= =你懂的），而小涛会的英雄有很多，小明每次和小涛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="" />

题目输入

第一行T，输入的组数。

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

题目输出

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

如果小明在选择最优对阵情况下可以从小涛那里获得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”。

输入/输出样例

输入格式

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

输出格式

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

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;
}

Java解答

import java.util.Scanner;
class Main<AnyType> {
	Node firstNode=new Node(0);
	Node secondNode=new Node(0);
	int sizeA=1;
	int sizeB=1;
	public int getSizeA() {
		return sizeA;
	}
	public int getSizeB() {
		return sizeB;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader = new Scanner(System.in);
		int T = reader.nextInt();
		for (int i = 0; i < T; i++) {
			int m = reader.nextInt();
			Main test = new Main();
			double[] a = new double[m];
			double[] b = new double[m];
			for (int j = 0; j < m; j++) {
				a[j] = reader.nextDouble();
			}
			for (int j = 0; j < m; j++) {
				b[j] = reader.nextDouble();
			}
			test.sort(a);
			test.sort(b);


			test.create1(test.firstNode, a);
			test.create2(test.secondNode, b);
			
			int sum = test.abcd();
			if (sum >= 0) {
				System.out.println("Xiaoming will get " + sum + "QB");
			} else {
				System.out.println("Xiaotao will get " + Math.abs(sum) + "QB");
			}

		}
	}

	// 计算sum并返回
	public <AnyType extends Comparable<? super AnyType>> int abcd(
			) {
		int sum = 0;
		
		while (firstNode.next!=null) {
			Node p=firstNode.next;
			Node q=secondNode.next;
			if (p.data > q.data) {
				sum=sum+200;
				remove1(1);
				remove2(1);
			}if (p.data == q.data) {
				Node c=getNode(getSizeA(),firstNode);
				Node d=getNode(getSizeB(),secondNode);
				if(c.data<=d.data&&c.data!=p.data){
					remove1(1);
					remove2(getSizeB()-1);
					sum=sum-200;
				}else if(c.data>d.data){
					remove1(getSizeA()-1);
					remove2(getSizeB()-1);
					sum=sum+200;
				}else if(c.data==d.data&&c.data==p.data){
					remove1(getSizeA()-1);
					remove2(getSizeA()-1);
				}
			}if (p.data < q.data) {
				sum=sum-200;
				remove1(1);
				remove2(getSizeB()-1);
			}
		}
		return sum;
	}
	//获得idx位置的节点
	public Node getNode(int idx,Node node){
		Node p=node;
		for(int i=0;i<idx-1;i++){
			p=p.next;
		}
		return p;
	}
	// 删除单链表中的元素
	public void remove1(int idx){
		Node p=firstNode;
		for(int i=0;i<idx-1;i++){
			p=p.next;
		}
		Node node=p.next.next;
		p.next=node;
		sizeA--;
	}
	public void remove2(int idx){
		Node p=secondNode;
		for(int i=0;i<idx-1;i++){
			p=p.next;
		}
		Node node=p.next.next;
		p.next=node;
		sizeB--;
	}
	// 对数组进行构造单链表
	public void create1(Node node, double[] a) {
		Node p = node;
		for (int i = 0; i < a.length; i++) {
			p.next = new Node(a[i]);
			p = p.next;
			sizeA++;
		}
	}
	public void create2(Node node, double[] a) {
		Node p = node;
		for (int i = 0; i < a.length; i++) {
			p.next = new Node(a[i]);
			p = p.next;
			sizeB++;
		}
	}
	// 对输入的数组进行排序
	public void sort(double[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j < a.length - 1; j++) {
				if (a[j + 1] < a[i]) {
					double c = a[j + 1];
					a[j + 1] = a[i];
					a[i] = c;
				}
			}
		}
	}

	// 节点类
	private static class Node {
		double data;
		Node next;

		Node() {
		}

		Node(double date) {
			this.data = date;
			this.next = null;
		}

		public Node(double d, Node n) {
			this.data = d;
			this.next = n;
		}
	}
}

上一题下一题代码讨论统计