训练部队

已知获胜战斗力值会加上对手的潜力值-对手的战斗力值。
贪心思想，要培养一个战力和潜力和最大的兵王，就要尽可能多的增加其战力，即打赢所有潜力大于战力的新兵，记他们的潜力战力差的总和为add。
选兵王，有两种情况：

1. 潜力qian大于战力zhan，不能与自己交战，所以要先从add中减去他的部分，最终兵王战力潜力和为add-(qian-zhan)+zhan+qian=add+2*zhan
2. 否则，直接加上他的潜力战力，即add+qian+zhan
   

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    long long maxZhan = 0, add = 0, maxSum = 0, tZhan, tQian;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> tZhan >> tQian;
        //潜力比战斗力大，记录潜力与战力差的总和和其中最高的战斗力
        if(tZhan < tQian)    maxZhan = max(maxZhan, tZhan), add += tQian - tZhan;
        //否则，记录最大的潜力、战力和
        else    maxSum = max(maxSum, tZhan + tQian);
    }
    cout << add + max(2 * maxZhan, maxSum) << endl;
    return 0;
}

【正确理解题意】①题中要求除了除了考察的那个新兵之外，其他新兵之间不会发生战斗②题中没有要求考察的新兵与所有剩下的新兵都决斗。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        Entity[] a = new Entity[n];
        for (int i = 0; i < n; i++) {
            a[i] = new Entity(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(a, new Comparator<Entity>() {
            @Override
            public int compare(Entity o1, Entity o2) {
                return o1.x-o2.x!=0 ? o1.x-o2.x : o1.y-o2.y;
            }
        });

        int max = 0; //x+y的最大值
        int index = 0; // 下标
        int cha = 0; // 差值
        for (int i = 0; i < n; i++) {
            if (a[i].x + a[i].y >= max || a[i].x + a[i].y + cha >= max) {
                max = a[i].x + a[i].y;
                cha = a[i].y - a[i].x;
                index = i;
            }
        }
        long res = max;
        for (int i = index-1; i >= 0 ; i--) {
            if (a[i].y > a[i].x) {
                res += a[i].y - a[i].x;
            }
        }

        System.out.println(res);
    }

    static class Entity {
        int x;
        int y;
        public Entity(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    long a[n][2];
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    long maxZ = 0, maxZQ = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        if (a[i][1] - a[i][0] > 0) {
            if (maxZ < a[i][0]) {
                maxZ = a[i][0];
            }
            sum += a[i][1] - a[i][0];
        } else {
            if (maxZQ < a[i][0] + a[i][1]) {
                maxZQ = a[i][0] + a[i][1];
            }
        }
    }
    if (2 * maxZ > maxZQ) {
        sum += 2 * maxZ;
    } else {
        sum += maxZQ;
    }
    cout << sum;
    return 0;
}

import java.util.*;
public class 训练部队{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Entity[] a = new Entity[n];
        for (int i = 0; i < n; i++) {
            a[i] = new Entity(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(a, new Comparator<Entity>() {
            @Override
            public int compare(Entity o1, Entity o2) {
                return o1.x-o2.x!=0 ? o1.x-o2.x : o1.y-o2.y;
            }
        });
        int max = 0; //x+y的最大值
        int index = 0; // 下标
        int cha = 0; // 差值
        for (int i = 0; i < n; i++) {
            if (a[i].x + a[i].y >= max || a[i].x + a[i].y + cha >= max) {
                max = a[i].x + a[i].y;
                cha = a[i].y - a[i].x;
                index = i;
            }
        }   
        long res = max;
        for (int i = index-1; i >= 0 ; i--) {
            if (a[index].x!=a[i].x&&a[i].y > a[i].x) {
                res += a[i].y - a[i].x;
            }
        }

        System.out.println(res);
    }
    static class Entity {
        int x;
        int y;
        public Entity(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
测试用例忽略了一些限制条件，就是与选中的人相同的战斗力的人之间是不能进行决斗的，
所以得把条件a[index].x!=a[i].x加上，就满足题意的要求了！

import java.util.Scanner;

/*
参考大神的解题思路：https://www.nowcoder.com/questionTerminal/79190c8e6202414bad33d6e287b61f3d
*
* 这道题目关键是理解题目意思，通俗的来说就是，从部队中挑选出一名战士，通过和其他人的斗争，可能获取到的最大值；
* 显然不能直接暴力，该战士只能与x<y（x代表战斗力，y代表潜能值）的人PK才能获取到经验值；
* 题目要求最大的x+y的值，通过比较可以求出战斗之后的sum(x-y)增量，还需要添加自己的能力值。
*
* 比较巧妙的地方就是，
* 1.如果该战士x<y的话，能力值已经计算过了，因此sum=sum-(y-x)+x+y=sum+2*x；
* 2.如果x>=y的话，sum = sum+x+y；
* 可以避免直接找到需要被训练的战士，只需要遍历中间过程找到x+y和2*x的最大值添加即可
* */
public class XunLeiSoldier {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            long sum = 0;
//            寻找的最大比较值
            long comparedVal = 0;
            for (int i = 0; i < n; i++) {
                long x = scanner.nextInt();
                long y = scanner.nextInt();
                if (x < y) {
//                    添加增量
                    sum += y - x;
                    comparedVal = Math.max(comparedVal, x + x);
                } else {
                    comparedVal = Math.max(comparedVal, x + y);
                }
            }
            System.out.println(comparedVal + sum);
        }
    }
}

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long x, y;
    long long sumdeta = 0,maxx = 0,maxxy = 0;
    for (int i = 0; i < n; i++){
        cin >> x >> y;
        if (y - x > 0){
            sumdeta += y - x;
            maxx = maxx > x ? maxx : x;
        }
        else
            maxxy = maxxy > (x + y) ? maxxy : (x + y);
    }
    if (sumdeta + maxxy > sumdeta + 2 * maxx)
        cout << sumdeta + maxxy;
    else
        cout << sumdeta + 2 * maxx;
}

package org.xwt.spring;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Soldier {
	
	private int capacity;
	private int potential;

	public int getCapacity() {
		return capacity;
	}
	public void setCapacity(int capacity) {
		this.capacity = capacity;
	}
	public int getPotential() {
		return potential;
	}

	public void setPotential(int potential) {
		this.potential = potential;
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len = sc.nextInt();
		List<Soldier> list = new ArrayList<Soldier>(len);
		for(int i=0;i<len;i++){
			Soldier soldier = new Soldier();
			soldier.setCapacity(sc.nextInt());
			soldier.setPotential(sc.nextInt());
			list.add(i, soldier);
		}
		list.sort(new Comparator<Soldier>() {
			@Override
			public int compare(Soldier o1, Soldier o2) {
				if(o1.getCapacity() == o2.getCapacity()){
					return o2.getPotential()-o1.getPotential();
				}
				return o1.getCapacity() - o2.getCapacity();
			}
		});
		//如果输入为空输出为0
		if(list.size() == 0){
			System.out.println(0);
		}else if(list.size() == 1 || list.get(0).getCapacity() == list.get(list.size()-1).getCapacity()){
			//如果只有一个战士，输出本身
			//如果所有战士战力值相等，输出潜力值最高的
			System.out.println(list.get(0).getCapacity()+list.get(0).getPotential());
		}else{
			//用战力值最高的战士去逐一决斗，累加所有的潜力
			Soldier s = list.get(list.size()-1);
			int c = s.getCapacity();
			for(int i =0;i<list.size()-1;i++){
				Soldier temp = list.get(i);
				if(temp.getCapacity() >= temp.getPotential()){
					//如果被决斗人战力大于或等于潜力，将不会被决斗
					continue;
				}
				c = c+temp.getPotential() - temp.getCapacity();
			}
			System.out.println(c+s.getPotential());
		}
		sc.close();
		
	}
	

}

要求：找出max(通过互相决斗之后新兵中战斗力值+潜力值).
获胜者战斗力 = (对手的潜力值 - 对手的战斗力值 )+ 自己的战斗力值 
max(战斗力 + 潜力) = (对手的潜力值 - 对手的战斗力值 )+ (自己的战斗力值 + 自己的潜力值)
第一部分保证为正直，即 对手的潜力值 >  对手的战斗力值

if 本人 自己的潜力值 < 自己的战斗力值: max(战斗力 + 潜力) = max(对手的潜力值 - 对手的战斗力值 ) + (自己的战斗力值 + 自己的潜力值)  保证max(自己的战斗力值 + 自己的潜力值) else:  max(战斗力 + 潜力) = max(对手的潜力值 - 对手的战斗力值 ) - (自己的潜力值 - 自己的战斗力值) + (自己的潜力值 + 自己的战斗力值) 
        = max(对手的潜力值 - 对手的战斗力值 )  + 2 * 自己的战斗力值
        保证 max(2 * 自己的战斗力值) 

因此，求 max(自己的战斗力值 + 自己的潜力值)，max(2 * 自己的战斗力值)，max((对手的潜力值 - 对手的战斗力值 ),
max1 = max(对手的潜力值 - 对手的战斗力值 ) + max(自己的战斗力值 + 自己的潜力值)
max2 = max(对手的潜力值 - 对手的战斗力值 ) + max(2 * 自己的战斗力值) 最终结果：max(max1, max2)

#-*-coding:utf-8-*- n = int(raw_input())

lis = []
sum_zhan_qian = 0
max_zhan_qian = 0
max_zhan = 0
max_xin = 0

for i in xrange(0, n):
    temp = raw_input()
    [x, y] = map(int, temp.split())
    lis.append([x, y])
    if lis[i][0] < lis[i][1]:
        sum_zhan_qian = sum_zhan_qian + lis[i][1] - lis[i][0]
        temp = 2 * lis[i][0]
        if temp > max_zhan:
            max_zhan = temp
    else:
        temp = lis[i][0] + lis[i][1]
        if temp > max_zhan_qian:
            max_zhan_qian = temp

max_xin = sum_zhan_qian + max(max_zhan_qian, max_zhan)
print max_xin

对不住大家了，之前由于牛客测试样例问题有一种情况没有考虑到，虽然ac了但是ac不是
目的，我们要追求严谨性，吐曹一秒牛客的测试样例。这里贴出更改之后的代码，更改处
有标记，这里对大家说声抱歉，同时提醒大家注意排除所有情况以及对牛客的答案要仔细
思考。
/* ***********************************************
Author        :wsw
Created Time  :2017年05月21日 星期日 22时55分09秒
TASK		  :Algorithm/date/牛客网/GG/xunlianbudui.cpp
LANG          :C++
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
struct soder{
	int x;
	int y;
};
int comp(soder s1,soder s2)
{
 return s1.x-s2.x!=0?s1.x<s2.x:s1.y<s2.y;
}
int main()
{
    int n,z,q;
	cin >> n;
	soder ant[n];
	for(int i=0;i<n;i++){
		cin >> z >> q;
		ant[i].x=z;
		ant[i].y=q;
	}
	sort(ant,ant+n,comp);
	int max = 0;
	int index = 0;
	int cha = 0;
	for(int i=0;i<n;i++){
		if(ant[i].x+ant[i].y>=max||ant[i].x+ant[i].y+cha>=max){
			max = ant[i].x+ant[i].y;
			cha = ant[i].y-ant[i].x;
			index = i;
		}
        //此处判断战斗力相同情况下的情况
        if(i>0&&ant[i].x==ant[i-1].x)
            {
            max = 0;
        }
        
	}
	long res = max;
	if(res>0){
	for(int j = index-1;j>=0;j--){
		if(ant[j].y>ant[j].x){
			res += ant[j].y-ant[j].x;
		}
	}
	cout << res << endl;
	}else{
	cout << 0 << endl;
	}
    return 0;
}  /* ***********************************************
Author        :wsw
Created Time  :2017年05月21日 星期日 22时55分09秒
TASK		  :这道题其实思想很简单，需要点数学功底，搞明白潜力型的总值是固定的，只需要找到一个最合适的
战斗型人才就行  LANG          :C++
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
struct soder{
	int x;
	int y;
};
int comp(soder s1,soder s2)
{
 return s1.x-s2.x!=0?s1.x<s2.x:s1.y<s2.y;
}
int main()
{
    int n,z,q;
	cin >> n;
	soder ant[n];
	for(int i=0;i<n;i++){
		cin >> z >> q;
		ant[i].x=z;
		ant[i].y=q;
	}
	sort(ant,ant+n,comp);
	//cout << " ssss " << endl;
	int max = 0;
	int index = 0;
	int cha = 0;
	for(int i=0;i<n;i++){
		if(ant[i].x+ant[i].y>=max||ant[i].x+ant[i].y+cha>=max){
			max = ant[i].x+ant[i].y;
			cha = ant[i].y-ant[i].x;
			index = i;
		}
	}
	long res = max;
	for(int j = index-1;j>=0;j--){	
		if(ant[j].y>ant[j].x){
			res += ant[j].y-ant[j].x;
			//cout << res << "+++" << endl;
		}
	}
	cout << res << endl;
    return 0;
}