首页 > 试题广场 >

塔

[编程题]塔
  • 热度指数：20286 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小易有一些立方体，每个立方体的边长为1，他用这些立方体搭了一些塔。
现在小易定义：这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。
小易想让这些塔尽量稳定，所以他进行了如下操作：每次从某座塔上取下一块立方体，并把它放到另一座塔上。
注意，小易不会把立方体放到它原本的那座塔上，因为他认为这样毫无意义。
现在小易想要知道，他进行了不超过k次操作之后，不稳定值最小是多少。

输入描述:
第一行两个数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
算法知识视频讲解
添加回答
这把稳吃鸡头像 这把稳吃鸡 
mport 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();//最多操作数
       ArrayList<Integer> towers=new ArrayList<>();
       for (int i=0;i<n;i++)
           towers.add(sc.nextInt());
       int count=0;
       int max=Collections.max(towers);
       int min=Collections.min(towers);
       ArrayList<Integer> list1=new ArrayList<>();
       ArrayList<Integer> list2=new ArrayList<>();
       while (max-min>1&&count<k)
       {
           max=Collections.max(towers);min=Collections.min(towers);
           list1.add(towers.indexOf(max)+1);list2.add(towers.indexOf(min)+1);
           towers.set(towers.indexOf(min),min+1);
           towers.set(towers.indexOf(max),max-1);
           count++;
       }
       System.out.println(Collections.max(towers)-Collections.min(towers)+" "+count);
       for (int i=0;i<list1.size();i++)
       {
           System.out.println(list1.get(i)+" "+list2.get(i));
       }
   }
}
java的collection的函数各种调用，思路和上面答案差不多，利用函数使代码更加简洁
发表于 2019-04-02 12:53:16 回复(4)
Java
Mono_Chrome头像 Mono_Chrome

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)
疯小子头像 疯小子 

	import java.util.ArrayList;





	import java.util.Scanner;





	 





	public class Main {





	    public static void main(String[] args) {





	        Scanner scan = new Scanner(System.in);





	        int n = scan.nextInt();//塔数





	        int k = scan.nextInt();//最多可操作数





	        int[] height = new int[n];//塔的高度





	        for (int i = 0; i < n; i++) {





	            height[i] = scan.nextInt();





	        }





	        int count = 0;





	        ArrayList<Integer> list1 = new ArrayList<Integer>();





	        ArrayList<Integer> list2 = new ArrayList<Integer>();





	        for (int i = 0; i < k; i++) {





	            int h = max(height);//找到最高的





	            int l = min(height);//找到最低的





	            if(balance(height[h],height[l])) {





	                break;





	            }





	            count++;





	            height[h]--;





	            height[l]++;





	            list1.add(h+1);





	            list2.add(l+1);





	        }





	        System.out.println(height[max(height)]-height[min(height)]+" "+count);





	        for (int i = 0; i < list1.size(); i++) {





	            System.out.println(list1.get(i)+" "+list2.get(i));





	        }





	        





	    }





	    





	    public static int max(int[] height) {//返回最高塔的下标





	        int h = 0;





	        int max = height[0];





	        for (int i = 1; i < height.length; i++) {





	            if(max<height[i]) {





	                h = i;





	                max = height[i];





	            }





	        }





	        return h;





	    }





	





	    public static int min(int[] height) {//返回最低塔的下标





	        int l = 0;





	        int min = height[0];





	        for (int i = 1; i < height.length; i++) {





	            if(min>height[i]) {





	                l = i;





	                min = height[i];





	            }





	        }





	        return l;





	    }





	    





	    public static boolean balance(int hval,int lval){//判断是否平衡





	        boolean flag = false;





	        int x = hval-lval;





	        if(x<=1)





	            flag = true;





	        return flag;    





	    }





	}

发表于 2018-09-02 10:10:32 回复(4)
笋也可以头像 笋也可以

策略很简单，就是每次把最高的塔拆一个到最低的上面，题目的坑在于，如果最后几步的不稳定值没变，可以选择不做最后几步

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <cstdio>
using namespace std;


int main()
{
    int n, k;
    cin>>n>>k;
    vector<int> res, h(n, 0), st;
    for(int i=0; i<n; ++i) cin>>h[i];
    while(1){
        auto b=h.begin(), s=h.begin();
        for(auto it = h.begin(); it != h.end(); ++it){
            if(*it > *b) b = it;
            if(*it < *s) s = it;
        }
        st.push_back(*b - *s);
        if(st.size()>k || *b - *s < 2) break;
        res.push_back(b - h.begin() + 1);
        res.push_back(s - h.begin() + 1);
        --*b; ++*s;
    }
    while(st.size()>1 && *(st.end()-2) == *(st.end()-1))
        st.pop_back();
    int m = st.size() - 1;
    cout<<st.back()<<' '<<m<<endl;
    for(int i=0; i<m; ++i){
        cout<<res[2*i]<<' '<<res[2*i+1]<<endl;
    }
}
发表于 2018-08-15 00:55:32 回复(6)
C/C++
道可道非常道嘤头像 道可道非常道嘤
我发现了，好多这种类型的题，声明pair类型的vector解决很方便
思路：
a容器的数值对first记索引，second记初始值；
b容器的数值对first记被取的塔索引+1，second记索取的塔索引+1；
将a数值对根据初始值(second)从小到大排序，如果最大值比最小值大，最大值a[n-1]的second+1，最小值a[0]的second-1；，然后将两个值对应的索引值push到b容器就行了，重复此过程直到平衡值为0或者次数用光； 
#include<bits/stdc++.h>
using namespace std;
bool op(const pair<int, int>a, const pair<int, int>b);
int main() {
	int n, k, x, s, m = 0;
	cin >> n >> k;
	vector<pair<int, int>>a, res;
	for (int i = 0; i<n; i++) {
		cin >> x;
		a.push_back(make_pair(i, x));
	}
	sort(a.begin(), a.end(), op);
	while (k--) {
		if (a[n - 1].second>a[0].second) {
			m++;
			a[n - 1].second--;
			a[0].second++;
			res.push_back(make_pair(a[n - 1].first+1, a[0].first+1));
			sort(a.begin(), a.end(), op);
		}
		else break;
	}
	s = a[n - 1].second - a[0].second;
	cout << s <<" "<< m << endl;
	for (int i = 0; i<m; i++) {
		cout << res[i].first << " " << res[i].second << endl;
	}
	return 0;
}
bool op(const pair<int, int>a, const pair<int, int>b) {
	return a.second<b.second;
}


编辑于 2019-09-17 17:08:23 回复(4)
我是雷蒙德头像 我是雷蒙德
思路： 其实很简单，每次排个序，然后从最大堆往最小堆搬一个即可，并记录堆序号，直到最大堆-最小堆<1 或者 移动次数达到k。这里排序并保留堆序号的方法，是用的python内置的sort()函数，当然也可以调用 numpy的argsort()。 
# -*- coding: utf-8 -*-
 
# 为后面排序定义一个方法
def by_value(t):
    return t[1]
 
# 读入数据
n,k = list(map(int, input().split()))
A = list(map(int, input().split())) # A = [a1,a2,a3,...an]
#eg：
#n,k = [3,2]
#A = [5,8,5]
 
# A_ = [[1, 5], [2, 8], [3, 5]] 其中每个元素表示：[第i堆，对应塔数]
A_ = [list(i) for i in zip (range(1,len(A)+1),A)]
 
# 先对A_从大到小排一次序
sorted_A =sorted(A_, key = by_value, reverse = True)
count = 0
move_record = [] # 缓存搬移的记录
 
while sorted_A[0][1]-1 >= sorted_A[-1][1]+1 and count+1 <= k:
    max_index = sorted_A[0][0]
    min_index = sorted_A[-1][0]
    sorted_A[0][1] -=1    # 从最多堆搬走一个
      sorted_A[-1][1] +=1  # 往最少堆搬来一个
    count +=1
    move_record.append([max_index, min_index])
    sorted_A = sorted(sorted_A, key = by_value, reverse = True)
     
s = sorted_A[0][1]-sorted_A[-1][1]     # s:最小的不稳定值，即最小的差
print('{} {}'.format(s,count))
for i in move_record:
    print('{} {}'.format(i[0],i[1]))

编辑于 2018-08-14 02:09:38 回复(6)
QING0304头像 QING0304 
n, k = map(int, input().split())
a = list(map(int, input().split()))

res_list = []
for i in range(k):
    max_index = a.index(max(a))
    min_index = a.index(min(a))

    res_list.append([max_index+1, min_index+1])

    a[max_index] -= 1
    a[min_index] += 1

    if max(a) - min(a) < 2:
        break

print("%d %d" % (max(a)-min(a), len(res_list)))

for i in range(len(res_list)):
    print("%d %d" % (res_list[i][0], res_list[i][1]))

发表于 2018-08-20 20:48:44 回复(1)
lentolove头像 lentolove 
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Tal {
    int h, index;

    Tal(int h, int index) {
        this.h = h;
        this.index = index;
    }
}


public class Main {
    /**
     * 思想：借助大小优先队列每次取出最高塔和最低的塔进行操作，操作完之后再放回去
     * 直至出现最大最小塔的高度差为1或者可用的移动次数用完。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//塔的数量
        int k = sc.nextInt();//最多操作次数
        PriorityQueue<Tal> minque = new PriorityQueue<>(n, new Comparator<Tal>() {
            @Override
            public int compare(Tal o1, Tal o2) {
                return o1.h - o2.h;
            }
        });
        PriorityQueue<Tal> maxque = new PriorityQueue<>(n, new Comparator<Tal>() {
            @Override
            public int compare(Tal o1, Tal o2) {
                return o2.h - o1.h;
            }
        });
        Tal tal = null;
        for (int i = 1; i <= n; i++) {
            int t = sc.nextInt();
            tal = new Tal(t, i);
            minque.add(tal);
            maxque.add(tal);
        }
        int s = 0;//最小稳定值
        int times = 0;//移动次数
        //记录移动的索引
        int[][] move = new int[k][2];
        while (times < k) {
            Tal min = minque.poll();//最低的塔
            Tal max = maxque.poll();//最高的塔
            //如果最低塔和最高塔高度相等或者相差为1，就没必要继续了
            if (max.h - min.h <= 1) {
                break;
            }
            //最低塔高度增加1，最高塔高度减少1
            min.h = min.h + 1;
            max.h = max.h - 1;
            move[times][0] = max.index;
            move[times][1] = min.index;
            minque.add(min);
            maxque.add(max);
            times++;
        }
        s = maxque.peek().h - minque.peek().h;
        System.out.println(s + " " + times);
        for (int i = 0; i < times; i++) {
            System.out.println(move[i][0] + " " + move[i][1]);
        }
    }
}
发表于 2019-07-27 15:01:22 回复(1)
to_check头像 to_check
set维护即可 ，每次维护一个按照高度递增的二元组 ，取出首元素和尾元素，然后比较，若高度相同，则结束循环，否则，将尾元素减1，首元素加1，记录此时的操作编号。时间复杂度O(k logn) 
#include <bits/stdc++.h>
using namespace std;
set <pair<int,int> > s;
vector<pair<int,int> > mov;
int main(){
    int n,k,h;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&h);
        s.insert({h,i+1});
    }
    set <pair<int,int> >::iterator it;
    int ans = k;
    for(int i=1;i<=k;i++){
        it = s.end();
        it--;
        int h1 = (*s.begin()).first ,h2 = (*it).first;
        if(h1 == h2) { ans = i;break;}
        int pos1 =(*s.begin()).second, pos2 =(*it).second;
        s.erase(*s.begin());
        s.erase(*it);
        s.insert({h1+1,pos1});
        s.insert({h2-1,pos2});
        mov.push_back({pos2,pos1});
    }
    it = s.end(),it--;
    int h1 = (*s.begin()).first ,h2 = (*it).first;
    printf("%d %d\n",h2-h1,ans);
    for(int i=0;i<mov.size();i++) printf("%d %d\n",mov[i].first,mov[i].second);
}

发表于 2019-06-28 09:41:04 回复(2)
C/C++
热情(^-^)头像 热情(^-^) 
#include<iostream>
using namespace std;
int main(){
    int n,k,tempInt;
    int s;
    cin>>n>>k;
    int a[n][2],m[k][2];
    for(int i=0;i<n;i++){
        cin>>a[i][0];
        a[i][1]=i+1;
    } 
//数据输入完毕
    //计算数据输出，即不稳定度s和最小操作次数m
    //最大操作次数k，每次操作必定是由最高塔移到最低塔最合算
    //每次操作前后输入输出数据的类型不变
    //每次操作前进行如下判断：
    //如果最大值最小值两者相差小于2，此时停止操作    
    //否则每次操作对不稳定度的影响分为3种情况：
    //1.最大值和最小值唯一，此时s-2
    //2.最大值和最小值其中仅有一个不唯一，此时s-1
    //3.最大值和最小值都不唯一，此时s-0
    /*****************************改进算法*****************************/
    //每次操作前先统计出最大值和最小值集合，然后以最大值和最小值之差作为结束操作的一个判断参数（另一个判断参数为k）
    //最大值（maxSet）最小值(minSet)集合中的元素个数差，将作为s参数的更新依据，同时也是更新最大值最小值集合的依据
    //min{|maxSet|,|minSet|}将作为更新m参数的依据
    //****************************进一步改进*********************************
    //每次计算最大最小值集合都要遍历数组将是十分耗时的，所以不妨对塔高进行排序，这在k>n时比较有用
    //采用while循环，每次开始前进行判断与s参数以及m参数的更新
    //****************************冒泡排序a[n][2]从小到大排序************************************
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(a[j][0]>a[j+1][0]){
                tempInt=a[j][0];
                a[j][0]=a[j+1][0];
                a[j+1][0]=tempInt;
                tempInt=a[j][1];
                a[j][1]=a[j+1][1];
                a[j+1][1]=tempInt;
            }
        }
    }
    //****************************进行操作以及更新s和m参数*************************************
    s=0;
    int minCount,maxCount,opNum;
    while(s<k&&(a[n-1][0]-a[0][0])>=2){
        minCount=1;
        while(minCount<n&&a[minCount][0]==a[0][0])minCount++;
        maxCount=1;
        while(maxCount<n&&a[n-1-maxCount][0]==a[n-1][0])maxCount++;
        opNum=(maxCount<minCount)?maxCount:minCount;
        if(s+opNum>k)break;
        //记录操作
        for(int j=0;j<opNum;j++){
            (a[minCount-1-j][0])++;
            (a[n-maxCount+j][0])--;
            m[s+j][0]=a[n-maxCount+j][1];
            m[s+j][1]=a[minCount-1-j][1];
        }
        s+=opNum;
    }
    cout<<(a[n-1][0]-a[0][0])<<' '<<s<<endl;
    for(int j=0;j<s;j++){
        cout<<m[j][0]<<' '<<m[j][1]<<endl;
    }
    return 0;
}
发表于 2018-08-29 10:39:20 回复(1)
Java
pein531头像 pein531

贪心

每次从最高的塔上拿下一个立方体，放在最低的塔上。进行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)
Python
Jancydc头像 Jancydc 
def solution(k, hights):
    count = 1
    operation = []  # 存储操作步骤
    unstability = max(hights) - min(hights)
    while unstability > 1 and count <= k:
        maxhight_index = hights.index(max(hights))
        minhight_index = hights.index(min(hights))
        hights[maxhight_index] -= 1
        hights[minhight_index] += 1
        count += 1
        operation.append([maxhight_index+1, minhight_index+1])
        maxhight = max(hights)
        minhight = min(hights)
        unstability = maxhight - minhight
    count -= 1
    print(unstability, count)
    for i in operation:
        print(i[0], i[1])
if __name__ == '__main__':
    n, k = list(map(int, input().strip().split()))
    hights = list(map(int, input().strip().split()))
    solution(k, hights)

发表于 2020-06-16 12:37:30 回复(0)
zyyyyy还能再战头像 zyyyyy还能再战
简单贪心 
#include <bits/stdc++.h>
using namespace std;

int a[110];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++) {
        scanf("%d",a+i);
    }
    vector<pair<int,int>> ve;
    for (int i=0;i<k;i++) {
        auto p=max_element(a,a+n)-a;
        auto q=min_element(a,a+n)-a;
        if (a[p]==a[q]) break;
        --a[p];
        ++a[q];
        ve.push_back({p+1,q+1});
    }
    printf("%d %d\n",*max_element(a,a+n)-*min_element(a,a+n),ve.size());
    for (auto &p:ve) {
        printf("%d %d\n", p.first, p.second);
    }
    return 0;
}


编辑于 2020-05-13 09:23:29 回复(0)
C/C++
晶凌玄夜头像 晶凌玄夜 
//只排一次序，然后遍历k次。时间复杂度O(nlogn + k)
/*
模拟一下过程：假如塔高度分别是2， 9， 6， 3
排序：9 ， 6， 3， 2
第一步：9-->2;得 8， 6， 3， 3。 begin = 0. end = 3
第二步：8-->3.得 7， 6， 3， 4.  由于4比3大，那么前移一座塔，end = 2
第三步：7-->3.得 6， 6， 4， 4。 由于4小于6，那么4之前的塔都比它之后得塔高，end还原到最后一座。end = 3
第四步：6-->4.得 5， 6， 4， 5. 由于5比6小，begin++。5比4大，end--。begin = 1， end = 2
第五步：6-->4.得 5， 5， 5， 5.退出
5次可完成，不过有可能没有5次，无论到第几次，高度差都是 begin塔高 - end塔高。
因为我们每次移动后都保证begin的塔最高，而end的塔最低
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class solution
{
public:
    void GetMin(vector<pair<int, int> >& arr, int k, vector<pair<int, int> >& result)
    {
        if (arr.size() == 0) {
            return;
        }
        //先插入一个pair对象保存s，m
        result.push_back(make_pair(0, k));
        //排序，lambda表达式，不会的也可以自己定义函数，排的是降序(升序也行，不过后面的逻辑得反过来)
	    sort(arr.begin(), arr.end(), [=](const pair<int, int> a, const pair<int, int> b)
	    {
		    return a.first > b.first;
	    });
        int begin = 0;
        int end = arr.size() - 1;
        int times = k;
        while (begin < end && times > 0) {
            times--;
            result.push_back(make_pair(arr[begin].second + 1, arr[end].second + 1));
            arr[begin].first--;
            arr[end].first++;
            //如果前一座塔的高度已经小于它之后的那座塔的高度，那么begin++，下次就搬移++后的那座塔
            if (arr[begin].first < arr[begin + 1].first) {
                begin++;
            }
            //如果该座塔大于等于在它之后的塔，说明之前的塔都一样高，现在又从最开始那座塔搬移
            else {
                begin = 0;
            }
            //较低的塔跟较高的塔搬移规则是相反的，比前一座塔高则end--。否则，end = 末尾
            if (arr[end].first > arr[end - 1].first) {
                end--;
            }
            else {
                end = arr.size() - 1;
            }
            //他们的塔的高度一致就退出。因为我们的搬移的时候保证了begin前面的塔永远比end后面的塔高
            //所以begin和end两座塔高度相等，那么必然相邻或是同一座塔
            if (arr[begin].first == arr[end].first) {
                break;
            }
        }
        //最后begin位与end位塔高度差就是最小的不稳定值
        result[0].first = arr[begin].first - arr[end].first;
        result[0].second = k - times;
        return;
    }
};

int main()
{
    solution s;
    int n;
    int k;
    while (cin >> n >> k) {
        vector<pair<int, int> > arr(n);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i].first;
            arr[i].second = i;
        }
        vector<pair<int, int> > result;
        s.GetMin(arr, k, result);
        for (size_t i = 0; i < result.size(); ++i) {
            cout << result[i].first << " " << result[i].second << endl;
        }
    }
    return 0;
}

编辑于 2020-04-06 21:23:25 回复(1)
Java
xuebatian头像 xuebatian
import java.io.*;
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)
Java
惠鸿飞头像 惠鸿飞 
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)
Java
走码观花头像 走码观花 
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)
Python
我要扛offer回家头像 我要扛offer回家 
import sys
n,k=list(map(int,sys.stdin.readline().split()))
height=list(map(int,sys.stdin.readline().split()))
res=[]
for i in range(k):
    res.append([height.index(max(height))+1,height.index(min(height))+1])
    height[height.index(max(height))]-=1
    height[height.index(min(height))]+=1
print(str(max(height)-min(height))+' '+str(k))
for i in res:
    print(str(i[0])+' '+str(i[1]))

发表于 2019-08-19 14:14:01 回复(0)
只是不想说头像 只是不想说
构造二维数组，[编号，塔高]，按照塔高降序，编号升序排序，每次最大值-1，最小值+1，然后更新数组。跳出循环条件，k==0或者最大值-最小值<=1 
while True:
    try:
        n,k = map(int,input().split())
        arr = list(map(int,input().split()))
        for i in range(len(arr)):
            arr[i] = [i+1,arr[i]]
        arr.sort(key = lambda x:(x[1],x[0]),reverse = True)
        re = []
        kk = k
        while 1:
            if k==0 or arr[0][1]-arr[-1][1]<=1:
                break
            k-=1
            arr[0][1]-=1
            arr[-1][1]+=1
            re.append([arr[0][0],arr[-1][0]])
            l = 0
            r = -1
            while 1:
                if arr[l][1]<arr[l+1][1]:
                    arr[l],arr[l+1] = arr[l+1],arr[l]
                    l+=1
                else:
                    break
            while 1:
                if arr[r][1]>arr[r-1][1]:
                    arr[r],arr[r-1] = arr[r-1],arr[r]
                    r-=1
                else:
                    break
        s = abs(arr[0][1]-arr[-1][1])
        k = kk-k
        print(s,k)
        for i in re:
            print(' '.join(str(j) for j in i))
    except:
        break

发表于 2019-08-14 09:06:23 回复(0)
不知名～头像 不知名～
模拟这个过程，先进行排序，每次将最高的塔-1，最低的+1，经过每一轮都进行排序。而看数据量n<=100,k<=1000，完全可以使用这个方法，时间复杂度为O(k*nlogn)。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(vector<int> a, vector<int> b) {
return a[0] < b[0];
}

int main() {
        int n, k; cin >> n >> k;
        vector<vector<int>> height(n, vector<int>(2));
        int num = 0;
        for (int i = 0; i < n; i++) {
                cin >> num;
                //存入高度和所在位置
                height[i][0] = num;  height[i][1] = i + 1;
        }

        sort(height.begin(), height.end(), compare);
        vector<vector<int>> process;
        for (int i = 0; i < k; i++) {
                if (height[n - 1][0] > height[0][0]) {
                        height[n - 1][0]--; height[0][0]++;
                        process.push_back(vector<int>{height[n - 1][1], height[0][1] });
                        //每一轮进行重排序
                        sort(height.begin(), height.end(), compare);
                }
                if (height[n - 1][0] == height[0][0]) //全部高度一致时可以退出
                        break;
        }

        cout << height[n - 1][0] - height[0][0] << " " << process.size() << endl;
        for (int i = 0; i < process.size(); i++) {
                cout << process[i][0] << " " << process[i][1] << endl;
        }

         return 0;
}

编辑于 2019-08-02 11:18:50 回复(1)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 PHP工程师 排序 贪心 模拟 网易 2019 Java工程师
来自：网易2019秋季校园招...
上传者：小小
难度：
103条回答 18364浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号