采花生__牛客网

鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说:“你先找出花生最多的植株，去采摘它的花生;然后再找出剩下的植株里花生最多的，去采摘它的花生;依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件：
1. 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2. 从一棵植株跳到前后左右与之相邻的另一棵植株；
3. 采摘一棵植株下的花生；
4. 从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？
注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如花生田里只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为 13, 7, 15, 9。多多在 21 个单位时间内，只能经过(4, 2)、(2, 5)、(5, 4)，最多可以采到 37 个花生。

输入包含多组数据，每组数据第一行包括三个整数 M（1≤M≤20）、N（1≤N≤20）和 K（0≤K≤1000），用空格隔开；表示花生田的大小为 M * N，多多采花生的限定时间为 K个单位时间。
紧接着 M 行，每行包括 N 个自然数 P（0≤P≤500），用空格隔开；表示花生田里植株下花生的数目，并且除了0（没有花生），其他所有植株下花生的数目都不相同。

import java.util.Scanner; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; import java.io.BufferedInputStream; import java.lang.Math; public class pat1 { public static void main(String[] args) { Scanner in=new Scanner(new BufferedInputStream(System.in)); while(in.hasNext()) { Map<Integer,Integer> mapx=new HashMap<Integer,Integer>(); Map<Integer,Integer> mapy=new HashMap<Integer,Integer>(); int row=in.nextInt(); int col=in.nextInt(); int s=in.nextInt(); int[][] nut=new int[row][col]; int n=0; for(int i=0;i<row;i++) for(int j=0;j<col;j++) { nut[i][j]=in.nextInt(); if(nut[i][j]!=0) { mapx.put(nut[i][j],i+1); mapy.put(nut[i][j],j); n++; } } int[] seq=new int[n]; int time=0,ct=0,ect=0,end=0; for(Entry<Integer,Integer> entry: mapx.entrySet()) seq[--n]=entry.getKey(); time=mapx.get(seq[n])+1; System.out.println(n+" "+seq[n]); end=mapx.get(seq[n]); ect=seq[n++]; while((time+end)<=s) { ct+=ect; if(n>seq.length-1) break; time+=getTime(mapx.get(seq[n-1]),mapy.get(seq[n-1]),mapx.get(seq[n]),mapy.get(seq[n]))+1; end=mapx.get(seq[n]); ect=seq[n++]; } System.out.println(ct); } } static int getTime(Integer x1,Integer y1,Integer x2,Integer y2) { int len=0; len=Math.abs(x1-x2)+Math.abs(y1-y2); return len; } }

import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner input = new Scanner(System.in); while(input.hasNext()){ int m=input.nextInt(); int n=input.nextInt(); int k=input.nextInt(); int num=0; int num2=0; int a[][]=new int[m][n]; for (int i = 0; i < m; i ++) { for (int j = 0; j < n; j ++) { a[i][j] = input.nextInt(); } } int b[]=new int[2]; int c[]=new int[2]; b=findmax(a,m,n); if((2*(b[0]+1)+1)<=k){ num=(b[0]+2); num2+=a[b[0]][b[1]]; a[b[0]][b[1]]=0; } else num=k+1; while(num<k){ c=findmax(a,m,n); if((num+Math.abs(b[0]-c[0])+Math.abs(b[1]-c[1])+1+c[0]+1)<=k){ num+=(1+Math.abs(b[0]-c[0])+Math.abs(b[1]-c[1])); num2+=a[c[0]][c[1]]; a[c[0]][c[1]]=0; b[0]=c[0];b[1]=c[1]; } else{ break; } } System.out.println(num2); } } public static int[] findmax(int x[][],int m,int n){ int max=x[0][0]; int b[]=new int[2]; for (int i = 0; i < m; i ++) { for (int j = 0; j < n; j ++) { if(x[i][j]>max){ max=x[i][j]; b[0]=i;b[1]=j; } } } return b; } }

采花生

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题