英雄会在线编程题目（请大家不吝赐教）

港控/mmm° 2022-08-06 18:59 224阅读 0赞

最近看了一道英雄会在线编程题目，题目的介绍如下：

题目详情：

有一个数列，所有的数都是非负整数，你可以进行如下方式进行一次操作（注意一次完整的操作必须先后完成如下两个步骤）：（1） 任选一个不小于3的数，把它减少3。（2） 任选一个数把它增加1。请问，最多能够操作多少次？输入格式：多组数据，每组数据第一行是一个正整数n，表示数列中数的个数。(1<=n<=20000)第二行包含n个空格分隔的非负整数，每个整数不超过1000000。输出格式：对每组数据输出一行，表示最多可以进行的操作次数。<div class="l3" style="font-family: Simsun;font-size:14px;">                答题说明</div><div class="l_c3" style="font-family: Simsun;font-size:14px;">输入样例110210 11输出样例：410</div> 我想的是直接按照题目提供的算法来，这种方法很笨，但是我喜欢善始善终，尽然开始了，就尽量完成。现在程序能够正常运行，只是只能达到部分预期。只能计算出随机情况下的最大操作次数，无法计算出所有情况下最大的操作次数。此时又不能进行穷举法，走到这儿就觉得走不下去了，请大家不吝赐教。

package com.obob.forFun;
 
 import java.util.ArrayList;
 import java.util.Random;
 
 public class Test {
 	private static void calculate(ArrayList arr){
 		int length=0; //数组中数的个数
 		ArrayList array=new ArrayList(); //相应数组
 		int count=0; //最多能进行的次数
 		for(int i=0;i<arr.size()-1;i+=2){
 			length=(int)arr.get(i);
 			String val=arr.get(i+1).toString();
 			String []valOneByOne=val.split(" ");
 			for(int j=0;j<valOneByOne.length;j++){
 				array.add(Integer.valueOf(valOneByOne[j]));
 			}
 				while(true){
 					if(minusThree(array)){
 						plusOne(array);
 						count++;
 					}
 					else{
 						System.out.println("第"+(i/2+1)+"条数组最多能操作的次数： "+count);
 						break;
 					}
 						
 				}
 		}
 		return ;
 	}
 	private static boolean minusThree(ArrayList arr){
 		Random random=new Random(System.currentTimeMillis());
 		StringBuffer count=new StringBuffer(arr.size()); //计数器，记录在当前数组里查找的记录数
 //		System.out.println("count capacity:"+count.capacity());
 //		System.out.println("count length:"+count.length());
 		for(int i=0;i<arr.size();i++){ 
 //			count.setCharAt(i, '0');
 			count.append('0');
 		}
 			while(true){
 				int ranInt=random.nextInt(arr.size());
 				String s=count.toString();
 				
 				if(!s.contains("0")){
 					return false; //此时这个数组已经全部都小于3了，无法-3
 				}
 				if((int)arr.get(ranInt)>4){
 					arr.set(ranInt, (int)arr.get(ranInt)-3);
 					return true;
 				}
 				else{
 					count.setCharAt(ranInt, '1'); //数组下标为ranInt的地方已经小于3
 					continue;
 				}
 				
 			}
 	}
 	private static void plusOne(ArrayList arr){
 		Random random=new Random(System.currentTimeMillis());
 		while(true){
 			int ranInt=random.nextInt(arr.size());
 			if((int)arr.get(ranInt)<1000000){
 				arr.set(ranInt, (int)arr.get(ranInt)+1);
 				break;
 			}
 			
 		}
 		
 	}
 	public static void main(String []args){
 		ArrayList inputArray=new ArrayList();
 		for(int i=0;i<10;i++){
 			int j=0;
 			inputArray.add(j++, 10); //数组第一位存储第二位的整数个数
 			StringBuffer sbArray=new StringBuffer();
 			String s="";
 			Random random=new Random();
 			for(int k=1;k<11;k++){
 				sbArray.append(String.valueOf(random.nextInt(1000000)+1)+" ");
 				/*if(k%10==0){
 					System.out.println("\n");
 				}*/
 			}
 			inputArray.add(j, sbArray); //输入数组的初始化完成
 		}
 		calculate(inputArray);
 	}
 }