小易有一些立方体，每个立方体的边长为1，他用这些立方体搭了一些塔。
现在小易定义：这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。
小易想让这些塔尽量稳定，所以他进行了如下操作：每次从某座塔上取下一块立方体，并把它放到另一座塔上。
注意，小易不会把立方体放到它原本的那座塔上，因为他认为这样毫无意义。
现在小易想要知道，他进行了不超过k次操作之后，不稳定值最小是多少。
[编程题]塔
- 热度指数：20313 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行两个数n,k (1 <= n <= 100, 0 <= k <= 1000)表示塔的数量以及最多操作的次数。
第二行n个数，ai(1 <= ai <= 104)表示第i座塔的初始高度。
输出描述:
第一行两个数s, m，表示最小的不稳定值和操作次数(m <= k)
接下来m行，每行两个数x,y表示从第x座塔上取下一块立方体放到第y座塔上。
示例1
输入
3 2 5 8 5
输出
0 2 2 1 2 3
贪心
每次从最高的塔上拿下一个立方体，放在最低的塔上。进行k次，并在容器中记录每一次调整后塔群的不稳定值和具体的移动操作。
得到k次操作的不稳定值后，找到最小值对应的索引minIndex，输出前minIndex个移动操作即可。
import java.io.*;
import java.util.*;
class Node {
int id;
int height;
public Node(int id, int height) {
this.id = id;
this.height = height;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
String[] strs = br.readLine().split(" ");
Node[] tower = new Node[n];
for(int i = 0; i < n; i++){
int height = Integer.parseInt(strs[i]);
tower[i] = new Node(i, height);
}
int[] minmax = getMinMax(tower);
ArrayList<String> ops = new ArrayList<>();
ArrayList<Integer> unsteady = new ArrayList<>();
unsteady.add(tower[minmax[1]].height - tower[minmax[0]].height);
while(k-- > 0){
ops.add((tower[minmax[1]].id + 1) + " " + (tower[minmax[0]].id + 1));
tower[minmax[1]].height--;
tower[minmax[0]].height++;
minmax = getMinMax(tower);
unsteady.add(tower[minmax[1]].height - tower[minmax[0]].height);
}
int min = unsteady.get(0), index = 0;
for(int i = 1; i < unsteady.size(); i++){
if(unsteady.get(i) < min){
index = i;
min = unsteady.get(i);
}
}
if(index == 0){
System.out.println(min + " " + index);
}else{
System.out.println(min + " " + index);
for(int i = 0; i < index; i++){
System.out.println(ops.get(i));
}
}
}
private static int[] getMinMax(Node[] tower) {
int minIndex = 0, maxIndex = 0, min = tower[0].height, max = tower[0].height;
for(int i = 1; i < tower.length; i++){
if(tower[i].height < min){
min = tower[i].height;
minIndex = i;
}
if(tower[i].height > max){
max = tower[i].height;
maxIndex = i;
}
}
return new int[]{minIndex, maxIndex};
}
}
发表于 2022-03-03 21:31:46
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static void main(String[] args ){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();int k = sc.nextInt();
int[]ai = new int[n];
for(int i=0;i<n;++i) ai[i] = sc.nextInt();
int maxIndex = max(ai);
int minIndex = min(ai);
ArrayList<String> motion = new ArrayList<>();
for(int i=0;i<k;++i) {
if(ai[maxIndex]>ai[minIndex]) {
motion.add(ai[maxIndex]+" "+ai[minIndex]);
--ai[maxIndex];
++ai[minIndex];
maxIndex = max(ai);
minIndex = min(ai);
} else{
break;
}
}
System.out.println( (ai[maxIndex]-ai[minIndex])+" "+(motion.size()));
for(String value:motion) {
System.out.println(value);
}
}
public static int max(int[]p) {
int max=Integer.MIN_VALUE;
int pos=0;
for(int i=0;i<p.length;++i) {
if(p[i]>max) {
max = p[i];
pos = i;
}
}
return pos;
}
public static int min(int[]p) {
int min = Integer.MAX_VALUE;
int pos=0;
for(int i=0;i<p.length;++i) {
if(p[i]<min) {
min = p[i];
pos = i;
}
}
return pos;
}
}
AC
发表于 2020-03-01 17:37:34
回复(0)
import java.io.*;
public static void main(String[] args)throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] nk = bf.readLine().trim().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
int[][] data = new int[n][2];
nk = bf.readLine().trim().split(" ");
for(int i=0;i<n;i++){
data[i][0] = Integer.parseInt(nk[i]);
data[i][1] = i+1;
}
Arrays.sort(data, new Comparator<int[]>(){ //排序
public int compare(int[] o1, int[] o2) {
if(o1[0]==o2[0]){
return o1[1]-o2[1];
}
return o1[0]-o2[0];
}
});
int start = 0; //指向从左到右第一个最小值
int end = data.length-1;
while((end-1)>=0 && data[end][0]==data[end-1][0]){
end--; //指向从左到右第一个最大值
}
int s=data[end][0]-data[start][0],m=0; //最大值与最小值的差
int[][] step = new int[k][2]; //操作步骤记录数组
step[m][0] = data[end][1];
if(end==data.length-1){
while((end-1)>=0 && data[end][0]==data[end-1][0]){
end--;
}
}else{
end++;
}
step[m][1] = data[start][1];
if(data[start][0]<=data[start+1][0]){
start = 0;
}else{
start++;
}
m++;
s=data[end][0]-data[start][0];
}
System.out.println(s+" "+m);
for(int i=0;i<m;i++){
System.out.println(step[i][0]+" "+step[i][1]);
}
}
}
import java.util.*;
//思路 首先利用二维数组存储塔的高度和塔的位置 并将其排序，高度相同则按位置排序
//利用start和end指向（类比指针理解更容易）从左往右的第一个最小值和最大值（最大值和最小值可能出现多个）
//重点在于维护这两个指针 可多写几个例子辅助维护 时间复杂度在于第一次排序 nlogn 和后面每次更新之后查找最大值和最小值 n 相比每次更新后再排序应该算是优化了一点
public class Main{public static void main(String[] args)throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] nk = bf.readLine().trim().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
int[][] data = new int[n][2];
nk = bf.readLine().trim().split(" ");
for(int i=0;i<n;i++){
data[i][0] = Integer.parseInt(nk[i]);
data[i][1] = i+1;
}
Arrays.sort(data, new Comparator<int[]>(){ //排序
public int compare(int[] o1, int[] o2) {
if(o1[0]==o2[0]){
return o1[1]-o2[1];
}
return o1[0]-o2[0];
}
});
int start = 0; //指向从左到右第一个最小值
int end = data.length-1;
while((end-1)>=0 && data[end][0]==data[end-1][0]){
end--; //指向从左到右第一个最大值
}
int s=data[end][0]-data[start][0],m=0; //最大值与最小值的差
int[][] step = new int[k][2]; //操作步骤记录数组
while(s>1 && m<k){ //判定条件
//end的维护 因为end是从左到右第一个最大值，当他减小时，要分情况讨论
//1 end是数组边界 此时最大值需要重新找
//2 end不是数组边界，那么end一定超前移动
data[end][0]--;step[m][0] = data[end][1];
if(end==data.length-1){
while((end-1)>=0 && data[end][0]==data[end-1][0]){
end--;
}
}else{
end++;
}
// start的维护更加简单，要么往前加，要么回到0（此处建议写两个例子就明白了，主要在于数组一开始是升序的）
data[start][0]++;step[m][1] = data[start][1];
if(data[start][0]<=data[start+1][0]){
start = 0;
}else{
start++;
}
m++;
s=data[end][0]-data[start][0];
}
System.out.println(s+" "+m);
for(int i=0;i<m;i++){
System.out.println(step[i][0]+" "+step[i][1]);
}
}
}
发表于 2019-12-14 18:05:58
回复(0)
import java.util.*;
public class Main{
//思路和很多大佬差不多：
//(1)每次用最高塔减一，最低塔加一
//(2)约束条件为最高塔与最低塔的差<=1，或者操作次数大于最大操作次数
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//输入塔的数量
int k = sc.nextInt();//最多操作的次数
int[] heightOfTa = new int[n];//每座塔的初始高度
for(int i = 0; i < n; i++){
heightOfTa[i] = sc.nextInt();
}
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
int count = 0;//操作次数
for(int i = 0; i < k; i++){
//找到最高塔所在的下标
int max = findMax(heightOfTa);
//找到最低塔所在的下标
int min = findMin(heightOfTa);
//判断是否达到约束条件:(1)最高与最低塔之间最多相差1；（2）操作次数大于最大操作次数
if(arriveGoal(heightOfTa[max], heightOfTa[min]) || count > k){
break;
}
count++;//操作次数加1
heightOfTa[max]--;//最高塔放一个立方体到最低塔，高度减一
heightOfTa[min]++;//同时最低塔得到一个立方体，高度加一
list1.add(max + 1);//存放当前操作的下标便于输出,加一是因为原始下标是从0开始
list2.add(min + 1);
}
System.out.println(heightOfTa[findMax(heightOfTa)] - heightOfTa[findMin(heightOfTa)] + " " + count);
for(int i = 0; i < list1.size(); i++){
System.out.println(list1.get(i) + list2.get(i));
}
}
//寻找最高塔所在下标
public static int findMax(int[] heightOfTa){
int max = heightOfTa[0];
int maxIndex = 0;
for(int i = 0; i < heightOfTa.length; i++){
if(max < heightOfTa[i]){
maxIndex = i;
max = heightOfTa[i];
}
}
return maxIndex;
}
//寻找最低塔所在下标
public static int findMin(int[] heightOfTa){
int min = heightOfTa[0];
int minIndex = 0;
for(int i = 0; i < heightOfTa.length; i++){
if(min > heightOfTa[i]){
minIndex = i;
min = heightOfTa[i];
}
}
return minIndex;
}
//判断是否达到目标条件
public static boolean arriveGoal(int h1, int h2){
boolean isArrive = false;
if(h1 - h2 <= 1){
isArrive = true;
}
return isArrive;
}
}
发表于 2019-10-30 20:34:36
回复(0)
//这道题的思路是：先把它们排序， 然后每进行一次排序， 就把最高的向最低的移动一个
//然后， 把这个结果保存起来， 记录下此时的最高和最低， 循环进行操作之后，
//最后得到的值就是答案
//也就是说 这里得用到map来计算
//操作了多少次， 然后和距离都得保存， 最后， 按照稳定值排序， 决定最后输出的结果
import java.util.*;
public class Main{
public static void main(String [] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //塔的数量
int k = sc.nextInt(); //最多操作次数
int [] res = new int[k+1];
ArrayList <String> arr = new ArrayList();
int [] height = new int[n];
for(int i=0; i<n; i++)
{
height[i] = sc.nextInt(); //把数据存起来
}
int r = getNum(height);
res [0] = r;
// System.out.println("R:" + r);
if(r==0 || k ==0)
{
System.out.println(r + " 0");
return ;
}
for(int i=1; i<k+1; i++)
{
res[i] = Move(height, arr);
// System.out.println("res:"+res[i]);
}
//int min =Integer.MAX_VALUE;
int min =0;
for(int i=0; i<k+1; i++)
{
// min=min<res[i]?min:res[i];
if(res[min] > res[i])
{
min = i;
}
}
/* int i=0;
for(; i<k; i++)
{
if(min == res[i])
break;
}*/
// int index = min;
System.out.println(res[min] + " " + min);
// if(i==k)
for(int j=0;j<min; j++)
{
System.out.println((String)arr.get(j));
}
}
public static int Move(int [] num, ArrayList <String> arr)
{
int max_index = -1;
int max = -1;
int min = Integer.MAX_VALUE;
int min_index = -1;
for(int i=0; i<num.length; i++)
{
if(num[i]>max)
{
max = num[i];
max_index = i+1; //记录的是层数
}
if(num[i]<min)
{
min = num[i];
min_index = i+1;
}
}
num[max_index-1]--;
num[min_index-1]++;
String s = max_index + " " + min_index;
// System.out.println(num[max_index-1]-num[min_index-1]);
arr.add(s);
return getNum(num);// num[max_index-1]-num[min_index-1];
}
//获取一开始的差值
public static int getNum(int [] num)
{
// int max_index = -1;
int max = -1;
int m1 = Integer.MAX_VALUE;
// int min_index = -1;
for(int i=0; i<num.length; i++)
{
if(num[i]>max)
{
max = num[i];
// max_index = i+1; //记录的是层数
}
if(num[i]<m1)
{
m1 = num[i];
// min_index = i+1;
}
}
// num[max_index-1]--;
// num[min_index-1]++;
return max-m1;
}
}
//然后， 把这个结果保存起来， 记录下此时的最高和最低， 循环进行操作之后，
//最后得到的值就是答案
//也就是说 这里得用到map来计算
//操作了多少次， 然后和距离都得保存， 最后， 按照稳定值排序， 决定最后输出的结果
import java.util.*;
public class Main{
public static void main(String [] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //塔的数量
int k = sc.nextInt(); //最多操作次数
int [] res = new int[k+1];
ArrayList <String> arr = new ArrayList();
int [] height = new int[n];
for(int i=0; i<n; i++)
{
height[i] = sc.nextInt(); //把数据存起来
}
int r = getNum(height);
res [0] = r;
// System.out.println("R:" + r);
if(r==0 || k ==0)
{
System.out.println(r + " 0");
return ;
}
for(int i=1; i<k+1; i++)
{
res[i] = Move(height, arr);
// System.out.println("res:"+res[i]);
}
//int min =Integer.MAX_VALUE;
int min =0;
for(int i=0; i<k+1; i++)
{
// min=min<res[i]?min:res[i];
if(res[min] > res[i])
{
min = i;
}
}
/* int i=0;
for(; i<k; i++)
{
if(min == res[i])
break;
}*/
// int index = min;
System.out.println(res[min] + " " + min);
// if(i==k)
for(int j=0;j<min; j++)
{
System.out.println((String)arr.get(j));
}
}
public static int Move(int [] num, ArrayList <String> arr)
{
int max_index = -1;
int max = -1;
int min = Integer.MAX_VALUE;
int min_index = -1;
for(int i=0; i<num.length; i++)
{
if(num[i]>max)
{
max = num[i];
max_index = i+1; //记录的是层数
}
if(num[i]<min)
{
min = num[i];
min_index = i+1;
}
}
num[max_index-1]--;
num[min_index-1]++;
String s = max_index + " " + min_index;
// System.out.println(num[max_index-1]-num[min_index-1]);
arr.add(s);
return getNum(num);// num[max_index-1]-num[min_index-1];
}
//获取一开始的差值
public static int getNum(int [] num)
{
// int max_index = -1;
int max = -1;
int m1 = Integer.MAX_VALUE;
// int min_index = -1;
for(int i=0; i<num.length; i++)
{
if(num[i]>max)
{
max = num[i];
// max_index = i+1; //记录的是层数
}
if(num[i]<m1)
{
m1 = num[i];
// min_index = i+1;
}
}
// num[max_index-1]--;
// num[min_index-1]++;
return max-m1;
}
}
发表于 2019-09-04 20:35:35
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
*思路：找到数组中最大的和最小的，将最大的减一给最小的加一，这样即为一次操作，遍历 k
直至结束，或达到最稳定状态后提前退出，所以输出的 k 不一定等于给定的 k
*/
public class Main{
public static void main(String[]args){
//所有录入
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int a[] = new int[n];
for(int i = 0; i < n; i++){
a[i] = sc.nextInt();
}
//找出最小和最大，最大的减一，最小的加一
findmin(a,n,k);
}
private static void findmin(int[] a,int n,int k){
if(a.length > 0){
int i;
// l1 发送塔，送一个立方体给 l2
List<Integer> l1 = new ArrayList<Integer>();
// l2 是接收塔，从 l1 收到一个立方体
List<Integer> l2 = new ArrayList<Integer>();
int max = 0, min = 0;
for( i = 0; i < k; i++){
max = 0;
min = 0;
for(int j = 0; j < n; j++){
if(a[j] > a[max]){
max = j;
}
if(a[j] < a[min]){
min = j;
}
}//可能在k次数内就已经达到最大稳定，可以提前结束
if(a[max] - a[min] < 1){
break;
}else{
a[max]--;
a[min]++;
//最大和最小的位置记录下来，一会输出
l1.add(max+1);
l2.add(min+1);
}
}
//以上代码最后一次执行后，最大值最小值都变了，所以重新找到最大最小值，然后输出
min=0;
max=0;
for(int m=0;m<n;m++){
if(a[m]>a[max])
{
max=m;
}
if(a[m]<a[min]){
min=m;
}
}
System.out.println((a[max]-a[min]) +" "+i);
for(int k1 = 0; k1 < l1.size(); k1++){
System.out.println(l1.get(k1)+" " + l2.get(k1));
}
}
}
}
发表于 2019-08-20 11:41:15
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
String[] str1=buffer.readLine().split(" ");
int towerNum=Integer.parseInt(str1[0]);
int maxMoveNum=Integer.parseInt(str1[1]);
String[] str2=buffer.readLine().split(" ");
int[] towerInit=new int[towerNum];
for(int i=0;i<towerNum;i++){
towerInit[i]=Integer.parseInt(str2[i]);
}
int highTower=countMax(towerInit);
int lowTower=countMin(towerInit);
int m=0;
int highIndex=0,lowIndex=0;
int[][] move=new int[maxMoveNum][2];
for(int i=0;i<maxMoveNum;i++){
for(int j=0;j<towerNum;j++){
if(highTower<=towerInit[j]){
highIndex=j;
highTower--;
break;
}
}
for(int j=0;j<towerNum;j++){
if(lowTower>=towerInit[j]){
lowIndex=j;
lowTower++;
break;
}
}
towerInit[highIndex]--;
towerInit[lowIndex]++;
highTower=countMax(towerInit);
lowTower=countMin(towerInit);
m++;
move[i][0]=highIndex+1;
move[i][1]=lowIndex+1;
if(highTower-lowTower<=1){
break;
}
}
System.out.println((highTower-lowTower)+" "+m);
for(int k=0;k<m;k++){
System.out.println(move[k][0]+" "+move[k][1]);
}
}
private static int countMax(int[] arrays){
int max=arrays[0];
for(int i=0;i<arrays.length;i++){
if(max<arrays[i]){
max=arrays[i];
}
}
return max;
}
private static int countMin(int[] arrays){
int min=arrays[0];
for(int i=0;i<arrays.length;i++){
if(min>arrays[i]){
min=arrays[i];
}
}
return min;
}
}
1.首先创建两个方法，功能分别是计算一个数组的最大值与最小值。
2.调用1中的方法计算最高塔数和最低塔数。
3.创建局部变量：
m用来记录操作次数。
highIndex和lowIndex两个变量记录最高塔和最低塔的索引值.
move二维数组记录具体的操作。
4.使用循环。循环次数使用题目要求所给的最多操作次数。
(1)首先依次求出最高塔的索引 “highIndex“ 和最低塔的索引 “lowIndex”，并将相应位的最高塔数和最低塔数加1和减1。
(2)接着利用索引值“highIndex”和“lowIndex”改变最初的塔数数组值并根据该数组计算出最高塔数和最低塔数。
(3)利用局部变量m记录操作数，并将具体操作赋值给一个二维数组move。
5.输出：
最小的不稳定值即为最高塔数减去最低塔数。
具体操作则只需要输出二维数组move的前m个。
发表于 2019-07-15 22:06:26
回复(0)
Java
思路：每次都把数组进行排序，然后最大值-1，最小值+1，用ArrayList记录这一操作的痕迹。
import java.util.*;
public class Main {
static class Tower {
int height;
int index;
public Tower(int height, int index) {
this.height = height;
this.index = index;
}
}
public static class TowerComparator implements Comparator<Tower> {
public int compare(Tower t1, Tower t2) {
return t1.height - t2.height;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
Tower[] towers = new Tower[n];
for (int i = 0; i < n; i++) {
towers[i] = new Tower(sc.nextInt(), i + 1);
}
List<String> lists = new ArrayList<>();
Arrays.sort(towers, new TowerComparator());
int count = 0;
while (towers[n - 1].height - towers[0].height > 0 && k > 0) {
towers[n - 1].height--;
towers[0].height++;
k--;
count++;
lists.add(towers[n - 1].index + " " + towers[0].index);
Arrays.sort(towers, new TowerComparator());
}
System.out.println((towers[n - 1].height - towers[0].height) + " " + count);
for (int i = 0; i < lists.size(); i++) {
System.out.println(lists.get(i));
}
}
}
发表于 2019-06-30 15:51:55
回复(5)
问题信息
通过挑战的用户
查看代码-
2022-08-29 10:30:30
-
2022-08-17 10:20:32 -
2022-08-16 22:03:10
-
2022-08-13 23:26:14
-
2022-08-13 22:44:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
