CSES Introductory problem's algorithm - Increasing Array
21:31 02 Jul 2024

I am working around to resolve CSES Introductory problem's algorithm - Increasing Array via c++. I need help, please.

You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element. On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input The first input line contains an integer n: the size of the array. Then, the second line contains n integers x1, x2 ... xN the contents of the array.

Output

Print the minimum number of moves.

Example

Input: 5 3 2 5 1 7

Output: 5

My code is following

#include 
#include 
#include 
#include 
#include 
#include   
#include   
#include     
#include 
#include 
#include 
#include 
#include 
#include  
using namespace std;

int main()
{
    int arrSize = 0;
    int number = -1;
    vector vect;
    string s;

    std::string firstLine;
    std::getline(std::cin, firstLine);
    arrSize = stoi(firstLine); 

    std::string secondLine;
    std::getline(std::cin, secondLine);
    std::istringstream strm(secondLine);

    while (strm >> s)
    {
        std::istringstream(s) >> number;
        vect.push_back(number);
    }
    
    int cnt = 0; 
    
    for (int i = 0; i < arrSize - 1; i++)
    {
        for (int j = i + 1; j < arrSize; j++)
        {
            int first = vect[i];

            int second = vect[j];

            if (first > second)
            {
                std::swap(vect[i], vect[j]); 
                cnt++;
            }
        }
    }

    std::cout << cnt;

    return 0;
}

For the one of test cases input data are

10 6 10 4 10 2 8 9 2 7 7

and the correct output is by test

31

but my code returns

18

I understand here the "move" is in fact a swap. Cannot get the mistake...

Update #1

I've have tried different aproach like

int cnt = 0;
for (int i = 1; i < arrSize; ++i)
{
    if (vect[i] <= vect[i - 1])
    {
        cnt += vect[i - 1] - vect[i] + 1;
        int v = vect[i - 1] + 1;
        vect[i] = v;
        std::cout << vect[i] << "\t";
    }
} 

And get this result ( So I am incerasing the array but the correct output is 31.

I steel need help...

enter image description here

c++ visual-c++