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

输入描述:
第一行两个数n,k (1 <= n <= 100, 0 <= k <= 1000)表示塔的数量以及最多操作的次数。
第二行n个数,ai(1 <= a<= 104)表示第i座塔的初始高度。


输出描述:
第一行两个数s, m,表示最小的不稳定值和操作次数(m <= k)
接下来m行,每行两个数x,y表示从第x座塔上取下一块立方体放到第y座塔上。
示例1

输入

3 2
5 8 5

输出

0 2
2 1
2 3

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 回复(3)

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

#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)
思路: 其实很简单,每次排个序,然后从最大堆往最小堆搬一个即可,并记录堆序号,直到最大堆-最小堆<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)
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 回复(2)
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)
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)
我发现了,好多这种类型的题,声明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 回复(0)
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)
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 回复(2)
#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 回复(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)
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 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)
//每次选择塔中的最大值和最小值,记录其序号,然后将最大值-1,最小值加1,
//直到最大值和最小值相等或者达到规定次操作次数为止
def process(k,a):
    t = 0
    pr = []
    while(max(a)!=min(a) and t<k):
        pr.append([a.index(max(a))+1,a.index(min(a))+1])
        a[a.index(max(a))]-=1
        a[a.index(min(a))]+=1
        t+=1
    pr.append([max(a)-min(a),t])
    return pr
        
    
if __name__=='__main__':
    n,k = [int(i) for i in input().strip().split(' ')]
    a = [int(i) for i in input().strip().split(' ')]
    if len(a)!=n:
        print('wrong input')
    if n ==1:
        print('0 0')
    else:
        pr = process(k,a)
        print('%d %d\n'%(pr[-1][0],pr[-1][1]))
        for x,y in pr:
            print('%d %d\n'%(x,y))

发表于 2019-07-24 16:03:38 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct T{
    int index, height;
    T(){}
    T(int id, int h):index(id),height(h){}
};

bool cmp(T a, T b){
    if(a.height == b.height)
        return a.index > b.index;
    return a.height > b.height;
}

int main(){
    int n, k, s, m;
    cin>>n>>k;
    T t[n];
    for(int i=0;i<n;i++){
        int h;
        cin>>h;
        t[i] = T(i+1, h);
    }
    sort(t, t+n, cmp);
    vector<int> x, y;
    while(k--){
        if((t[0].height-t[n-1].height) <= 1)
            break;
        else{
            t[0].height--;
            t[n-1].height++;
            x.push_back(t[0].index);
            y.push_back(t[n-1].index);
            sort(t, t+n, cmp);
        }
    }
    s = t[0].height - t[n-1].height;
    m = x.size();
    cout<<s<<" "<<m<<endl;
    for(int i=0;i<m;i++)
        cout<<x[i]<<" "<<y[i]<<endl;
    return 0;
}

发表于 2019-07-08 02:45:52 回复(0)
n,k =list(map(int, input().split()))
a =list(map(int, input().split()))
p=[]
q=0
fori inrange(k):
    p.append(str(a.index(max(a))+1)+'\t'+str(a.index(min(a))+1))
    a[a.index(max(a))]-=1
    a[a.index(min(a))]+=1
    q+=1
    ifmax(a)-min(a)<=1:
                 break
 
print(str(max(a)-min(a))+'\t'+str(q))
fori inrange(len(p)):
    print(p[i])

发表于 2018-11-04 18:53:24 回复(0)

#include <iostream>

#include <map>

#include <vector>

using namespace std;


int main(){

    int k,n;

    while(cin>>n>>k){

        multimap<int, int> map;

        vector<int> source,obj;

        

        

        int num;

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

            cin>>num;

            map.insert(pair<int, int> (num, i));

        }

        multimap<int,int>::iterator it=map.end();

        multimap<int,int>::iterator min_it=map.begin();


        it--;

        int max=0;int maxi=0,min=0,mini=0;

        int count=0;

        while(k--&&it->first-min_it->first>1){

            count++;

            max=it->first;

            maxi=it->second;

            min=min_it->first;

            mini=min_it->second;

            source.push_back(maxi);

            obj.push_back(mini);

            map.erase(it);

            map.insert(pair<int, int> (max-1, maxi));

            map.erase(min_it);

            map.insert(pair<int, int> (min+1, mini));

            it=(--map.end());

            min_it=map.begin();

        }

        cout<<it->first-min_it->first<<' '<<count<<endl;


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

            cout<<source[i]+1<<' '<<obj[i]+1<<endl;

        }

   

    }


    return 0;

}


发表于 2018-09-10 16:07:29 回复(1)
importjava.util.Scanner;
publicclassMain {
 //在k次中,每次将最大值减一,最小值加一,并记录位置到2维数组中。直到k为0或最大值等于最小值
    publicstaticvoidmain(String[] args) {
     
        Scanner sc = newScanner(System.in);
        intn = sc.nextInt();
        intk = sc.nextInt();
        intMAX = 0,MIN = 10001;
        intMAXx = 0,MINy = 0;
        intk1 = k;
        int[][] num = newint[k][2];
        int[] nu = newint[n];
        for(inti = 0; i < n; i++) {
            nu[i] = sc.nextInt();
            MIN = MIN>nu[i]?nu[i]:MIN;
            MAX = MAX<nu[i]?nu[i]:MAX;
        }
        if(MAX!=MIN){
            while(k1-->0){
                for(inti = 0; i < n; i++) {
                    if(MAX<=nu[i]){
                        MAX = nu[i];
                        MAXx = i;
                    }
                    if(MIN>=nu[i]){
                        MIN = nu[i];
                        MINy = i;
                    }
                }
                if(MAX!=MIN){
                     
                    MIN = --nu[MAXx];
                    MAX = ++nu[MINy];
                    num[k-(k1+1)][0] = MAXx+1;
                    num[k-(k1+1)][1] = MINy+1;
                     
                }else{
                    break;
                }
            }
            MAX = 0;
            MIN = 10001;
            for(inti = 0; i < n; i++) {
                MIN = MIN>nu[i]?nu[i]:MIN;
                MAX = MAX<nu[i]?nu[i]:MAX;
            }
            System.out.println((MAX-MIN)+" "+(k-(k1+1)));
            for(inti = 0; i < k; i++) {
                System.out.println(num[i][0]+" "+num[i][1]);
            }
        }else{
            System.out.println("0"+" "+"0");
        }
    }
}
发表于 2018-08-24 10:42:55 回复(0)

热门推荐

通过挑战的用户

查看代码