还原数列

let n = Number(readline());
let arr = readline().split(' ');
let k = 0;
while(true){
    let maxIndex = 0;
    for(let i in arr){
        if(arr[i]>arr[maxIndex])maxIndex = i
    }
    let max = arr[maxIndex];
    if(max<n)break;
    let step = Math.floor(max/n);
    //print(step,max,n);
    for(let i in arr){
        if(i!=maxIndex)arr[i] = +arr[i] + step
    }
    arr[maxIndex]-=step*n
    k+=step
}
print(k)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        long[] num = new long[a];
        for (int i = 0; i < a; i++) {
            num[i] = sc.nextLong();
        }
        long k = 0;
        Arrays.sort(num);
        while (num[a - 1] >= a) {
            //注意两点：1 long  2 避免超时 max/n
            long tmp = num[a-1]/a;
            num[a - 1] -= a*tmp;
            for (int i = 0; i < a - 1; i++) {
                num[i] += tmp;
            }
            Arrays.sort(num);
            k+=tmp;
        }
        System.out.println(k);

    }
}

from heapq import *

n = int(input())
a = list(map(lambda s:-int(s), input().split()))

target_line = n
heapify(a)

op_time = 0
while True:
    peek = -a[0]
    if peek < target_line:
        print(op_time)
        break

    op = (peek - target_line) // (n+1) + 1

    after = peek - op * (n+1)
    heapreplace(a, -after)

    target_line -= op
    op_time += op

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

//注意范围
typedef long long ll;

int main(){
    int N;
    cin>>N;
    ll a[N];
    for(int i=0;i<N;i++){cin>>a[i];}
    ll res=0;
    while(true){
        sort(a,a+N);
        if(a[N-1]<N){break;}
        //主要是下面这三行，将多次减法用除法+取模解决了，然后加法那里记得要加的是商
        ll div=a[N-1]/N;
        a[N-1]=a[N-1]%N;
        for(int i=0;i<N-1;i++){a[i]+=div;}
        res+=div;
    }
    cout<<res<<endl;
    return 0;
}

n = int(input())
arr = input()
arr = arr.split(" ")
arr = list(map(int, arr))
k = 0
while True:
    tmp = max(arr)
    if tmp < n:
        break
    index = arr.index(tmp)
    arr = [x + tmp // n for x in arr]
    arr[index] = tmp % n
    k += tmp // n
print(k)

献丑c++代码，5ms

• 每次取最大值，计算减到小于n的次数k
• 更新值
  需要保证数组有序，可以在每次循环的时候排序，也能过，因为n的范围很小。但可以二分查找插入位置再插入，这样只需要开头排序一次。
  因为每次循环只减少最大值（数组末尾）的数值，其他数值（1～n-1）本身就是有序的，增加相同的值也是有序的，所以将的值插入进去就行了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    using ll = long long;
    multiset<ll> st;
    ll n;
    cin >> n;
    vector<ll> v;
    for (int k = 0; k < n; k++) {
        ll tmp;
        cin >> tmp;
        v.emplace_back(tmp);
    }
    std::sort(v.begin(), v.end());
    ll cnt = 0;
    while (v.back() >= n) {
        auto x = v.back();
        v.pop_back();
        ll k = (long long) (x * 1.0 / n - 1) + 1;
        cnt += k;
        x = x - k * n;
        for (auto& num : v) {
            num += k;
        }
        auto it = std::lower_bound(v.begin(), v.end(), x);
        v.insert(it, x);
    }
    cout << cnt;
}

/*

   构建大根堆实现
*/


import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main{
    public static int n;
    public static Long[]f;//构建的大根堆
    public static long k=0;
 
    //对大根堆的index节点进行右旋操作
    public static void sort(int index){
        int left=2*index+1,right=2*index+2;//左右子树顶点
 
        if(left<n&&right<n){
            long max =0;
            int i=left;
            if(f[left]>f[right]){
                max = f[left];
            }else{
                max = f[right];
                i=right;
            }
            //交换
            if(max>f[index]){
                long temp = f[index];
                f[index]=f[i];
                f[i]=temp;
                sort(i);//继续向下
            }
        }else if(left<n){
            if(f[left]>f[index]){
                //交换
                long temp = f[index];
                f[index]=f[left];
                f[left]=temp;
                sort(left);//继续向下
            }
        }
 
        return;
        
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n=in.nextInt();
        f = new Long[n];
         
        //输入数据
        for(int i=0;i<n;i++){
            f[i]=in.nextLong();
        }
 
        Arrays.sort(f,Collections.reverseOrder());
         
         
        while(f[0]>=n){
            //直接减多少个
            long t = f[0]/n;
            f[0]-=t*n;
            for(int i=1;i<n;i++){
                f[i]+=t;
            }
            k+=t;
            sort(0);
        }
 
        System.out.println(k);
         
        in.close();
    }
     
}

import java.util.Scanner;

/**
 * 还原数列
 */
public class Main5 {
    public static void main(String[] args) {
        long k=0;
        // xcrj
        int n=0;
        Scanner in=new Scanner(System.in);
        if(in.hasNextInt()){
            n=in.nextInt();
        }
        // xcrj
        long[] as=new long[n];
        for(int i=0;i<n&&in.hasNextLong();i++){
            as[i]=in.nextLong();
        }
        in.close();
        /**
         * 减法要想到/ %
         * 数组中的每个数字都会被减到小于n，遍历数组把每个数字都减到小于n
         * - as[i]/n, 被减ki次
         * - as[i]%n, 减ki次之后的余数, 是as[i]最后的值
         * - as[i]被减ki次，其它的数会加上ki个1
         */
        while(valid(as, n)){
            for (int i=0;i<n;i++){
                if(as[i]>=n){
                    long ki=as[i]/n;
                    k+=ki;
                    as[i]=as[i]%n;
                    for(int j=0;j<n;j++){
                        if(i!=j) {
                            as[j]+=ki;
                        }
                    }                
                }
            }
        }
        //
        System.out.println(k);
    }

    /**
     * 继续循环
     * 
     * @return true 存在as[i]>=n
     * @return false 不存在as[i]>=n
     */
    public static boolean valid(long[] as, int n) {
        for (long a : as) {
            if (a >= n) {
                return true;
            }
        }
        return false;
    }
}

# python
n = int(input())
nums = list(map(int, input().split()))
res = 0
# 模拟 一次减去times次数
while max(nums) >= n:
    index = nums.index(max(nums))
    times = (nums[index]-n)//n + 1
    nums = [item + times for item in nums]
    nums[index] -= times*(n+1)
    res += times
print(res)

import java.io.*;
import java.util.*;
public class Main{
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = " ";
        while((str = br.readLine()) != null){
            String[] str_array = br.readLine().split(" ");
            long n = (long)str_array.length;
            PriorityQueue<Long> heap = new PriorityQueue<>((o1,o2)->{return o1.compareTo(o2) < 0? 1 :-1;});
            for(String value : str_array) heap.offer(Long.parseLong(value));
            Queue<Long> queue = new LinkedList<>();
            long result = 0;
            while(true){
                long max = heap.poll();
                if(max < n) break;
                long step = max / n;
                queue.offer(max % n);
                while(heap.size() != 0) queue.offer(heap.poll()+step);
                while(queue.size() != 0) heap.offer(queue.poll());
                result += step;
            }
            System.out.println(result);
        }
    }
}

package com.ff.baidu;

import java.util.Arrays;

public class unit2 {
    /*给一个长度为n的数组，每次都用数组中最大的数-n,
    其他的数+1，执行多少次数组里面所有的数都小于n*/
    public static int getCount(int[] arr){
//       计算数组的长度
        int n=arr.length;
        int count=0;//计录一共进行了多少次
        while (true){
//            给数组排序
            Arrays.sort(arr);
            if(arr[arr.length-1]<n){
                break;
            }
//            数组中最大的数-n
            arr[arr.length-1]=arr[arr.length-1]-n;
//            让其他数加1
            for (int i = 0; i <arr.length-1 ; i++) {
                arr[i]+=1;
            }
            count++;

        }

        return count;
    }

    public static void main(String[] args) {
       int [] arr={1,7,4};
        int count =getCount(arr);
        System.out.println(count);
    }
}