[Problem Description]
Little A has an array consisting of n non-negative integersa=[a₁，a₂，a₃，…，aₙ] . He will repeatedly perform the following operations on the array a until the array a only contains 0. In one operation, Little A will sequentially complete the following three steps:
1、Find the largest integer in the array a, and denote its index as k. If there are multiple maximum values, choose the one with the largest index.
2、Find the smallest integer among all non-zero integers in the array a, denoted as aⱼ.
3、Subtract the integer found in the first step aₖ by aⱼ.
For example, the array a=[2,3,4] needs 7 operations to become [0,0,0] ：
[2,3,4]→[2,3,2]→[2,1,2]→[2,1,1]→[1,1,1]→[1,1,0]→[1,0,0]→[0,0,0]Little A wants to know how many operations are needed to turn all integers in the given array a into 0. It can be proven that the integers in a can all be turned into 0 after a finite number of operations. Can you help him calculate the answer?
[Input Format]
The first line contains a positive integer n, representing the length of the array a.
The second line contains n non-negative integers a₁，a₂，a₃，…，aₙ, representing the integers in the array a.
[Output Format]
One line, a positive integer, representing the number of operations required to turn all integers in a into 0 .
[Input Output Example]
Input1：
32 3 4Output1：
7Input2：
51 3 2 2 5Output2：
13[Note/Hint]
For all test cases, it is guaranteed that 1≤n≤100,0≤aᵢ≤100.
[Problem Analysis]
The problem requires simulating a specific operation process:
1、Find the maximum number in the array (if there are multiple maximum values, choose the one with the largest index);
2、Find the smallest non-zero number in the array;
3、Subtract the maximum number found in the first step by the smallest non-zero number found in the second step;
Repeat this process until all numbers become 0.
[Solution Approach]
A direct simulation method can be used:
1、Simulate one operation in each loop
2、Use sorting to simplify the search process
3、Use a loop to determine when the maximum value is 0 to end
[Program Code Analysis]
#include<bits/stdc++.h>using namespace std;int main(){ int n,m,k; int a[105]; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1); // Initial sorting k=0; // Operation counter while(a[n]!=0) // Continue while the maximum value is not 0 { for(int i=1;i<=n;i++) { if(a[i]!=0) // Find the first non-zero number (i.e., the smallest non-zero number) { a[n]-=a[i]; // Subtract the smallest non-zero number from the maximum value break; } } sort(a+1,a+n+1); // Re-sort k++; // Increment operation count } cout<<k<<endl; return 0;}[Algorithm Steps Analysis]
1、Initialization：Read data and sort.
2、Loop Operations：
① Find the first non-zero number (after sorting, this is the smallest non-zero number);
② Subtract the maximum value by this smallest non-zero number;
③ Re-sort the array;
④ Increment the operation counter;
3、Termination Condition：Stop when the maximum value is 0.
[Problems with the Program]
1、Logical Errors
The above program assumes that after sorting, <span><span>a[n]</span></span> is always the maximum value, and <span><span>a[i]</span></span> (the first non-zero number) is always the smallest non-zero number. However, the problem requires：
① When there are multiple maximum values, choose the one with the largest index;
② Sorting will destroy the original index information, making it impossible to meet this requirement. (Here, students can think about why the submitted program can still pass despite not meeting the requirements?)
2、Efficiency Issues
① Each operation involves sorting, with a time complexity of O(k×n log n), where k is the number of operations
② In the worst case, the number of operations can be very large
[Optimization Methods]
Here, I provide two optimization ideas.
One is direct simulation, where we keep the index unchanged and directly loop to find the position of the maximum value with the largest index, mark it, and then loop to find the smallest non-zero number for calculation. Then repeat the above operations until the maximum number is 0.
The second is a purely mathematical method. Upon deep reflection, it is not difficult to find that this operation process is actually gradually reducing the differences between numbers. We can first count the total “reduction amount” needed for all numbers to become 0, and then analyze the overall reduction shared by each operation.