算法提高 求最大值

算法提高 求最大值  

时间限制：1.0s   内存限制：256.0MB

    

问题描述

　　给n个有序整数对ai bi，你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负，bi之和非负。

输入格式

　　输入的第一行为n，数对的个数
　　以下n行每行两个整数 ai bi

输出格式

　　输出你选定的数对的ai+bi之和

样例输入

5
-403 -625
-847 901
-624 -708
-293 413
886 709

样例输出

1715

数据规模和约定

　　1<=n<=100
　　-1000<=ai,bi<=1000

import java.math.BigInteger;
import java.util.*;  
public class Main {  
	/*
	 * 思路:先选取两数之和a[i][2]中的较大者，判断选定的数对是否符合条件，
	 * 若符合，动态更新,直到a[i][2]<0为止
	 * 郁闷，只得了83分
	 */
    public static void main(String args[]){  
      Scanner in=new Scanner(System.in);   
      int n=in.nextInt();
      if(n<=0)
    	  return ;
      int[][] a=new int[n][3];
      int[] b=new int[n];//辅助数组
      for(int i=0;i<n;i++){
    	  a[i][0]=in.nextInt();
    	  a[i][1]=in.nextInt();
    	  a[i][2]=a[i][0]+a[i][1];//存和
      }
      int sum=0,x=0,y=0;
      int k=n;
      while(k-->0){
    	  int max=a[0][2];
    	  for(int i=1;i<n;i++){//找最大值
    		  if(a[i][2]!=-1 && a[i][2]!=-2 && max<=a[i][2]){
    			  max=a[i][2];
    		  }
    	  } 
    	  if(max<0){//当查找到的最大值小于0,无须继续查找
    		  break;
    	  }
    	  for(int i=0;i<n;i++){//匹配最大值项 
    		 if(max==a[i][2]){
    			 if(x+a[i][0]>=0 && y+a[i][1]>=0){//对于符合条件的动态更新
    				 x+=a[i][0];
    				 y+=a[i][1];
    				 sum+=max;
    				 a[i][2]=-1;//标记为已搜索过的最大值
    				 //System.out.println(sum);
    			 }else{
    				 b[i]=a[i][2];
    				 a[i][2]=-2;//标记为已搜索过的暂且不符合条件的最大值   				 
//    				   3    
//    				   1 1
//    				   -3 6
//    				   2 2 
//    				   -3 6这一数对暂且不符合条件，但最终符合条件 

    			 }
    		 }
    	  }   
    	  //从不符合条件的最大值中挑选可能符合条件的
    	  for(int i=0;i<n;i++){
    		  if(a[i][2]==-2){
    			  if(x+a[i][0]>=0 && y+a[i][1]>=0){//对于符合条件的动态更新
     				 x+=a[i][0];
     				 y+=a[i][1];
     				 sum+=b[i];
     				// System.out.println(sum);
     				 a[i][2]=-1;//标记为已搜索过的最大值
     			 }
    		  }
    	  }
      }     
    	System.out.println(sum);
    }
}