用贪心策略均分纸牌(洛谷P1031题题解,Java语言描述)

题目要求

P1031题目链接
用贪心策略均分纸牌(洛谷P1031题题解,Java语言描述)
用贪心策略均分纸牌(洛谷P1031题题解,Java语言描述)

分析

我们一定要知道的是average,这个average其实就是每堆牌最终一定要达到的情况。

想要更简单的结果,那就可以用贪心策略,从某一侧开始,逐一的补齐或天选,反正就是达到均值即可。

接下来我们分析一下流程,从我们选好的一端的第一堆牌开始啦:

第一堆牌相差的牌只能由第二堆牌承担(给予或索要),把它补齐到要求的数额。
而第一堆牌达到要求了就不要管它,忽略即可,因为它唯一能影响和被影响的只是第二堆牌。
此时,第二堆牌就相当于新的第一堆牌,而一侧的第一堆牌已经是调好了,那就和没有一样,相当于只能继续向第三堆牌进发咯。
……重复上述操作……
如果当前牌直接就OK那就忽略本次并继续,否则每次调整就需要counter++。
某一堆牌被上一次调整以后变成负数是不要紧的,因为你正着看是被索取,反着看则是给予,可以说这样的步骤是可逆的。

分析到这份儿上,就可以写代码了啊~~

AC代码(Java语言描述)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt(), sum = 0, average = 0, counter = 0;
        int[] array = new int[num];
        for (int i = 0; i < num; i++) {
            int temp = scanner.nextInt();
            sum += temp;
            array[i] = temp;
        }
        scanner.close();
        average = sum / num;
        for(int i = 0; i < num; i++) {
            int temp = array[i] - average;
            if(temp != 0) {
                array[i+1] += temp;
                counter++;
            }
        }
        System.out.println(counter);
    }
}

猜你喜欢