Dãy số nhảy múa

Submit solution
Points: 3 (partial)
Time limit: 2.0s
Memory limit: 977M
Author:
nqson
Problem type

Một dãy số có \(n\) các con số đang tổ chức nhảy múa để cổ vũ các bạn thí sinh trong cuộc thi làm bài có kết quả tốt nhất. Mỗi con số sẽ chỉ nhảy một độ cao bằng đúng giá trị của số đó

Do các con số có độ cao không bằng nhau nên độ lệch tối đa của dãy số là giá trị con số nhảy cao nhất trừ đi giá trị con số nhảy thấp nhất

Ví dụ một dãy số có 4 con số: 5, 9, 7, 1

Để tính độ lệch tối đa, ta cần tìm số lớn nhất và số nhỏ nhất trong dãy số này.

Số lớn nhất trong dãy số là 9 và số nhỏ nhất là 1 -> Độ lệch tối đa = 9 - 1 = 8.

Vậy, độ lệch tối đa của dãy số này là 8.

Do các con số đứng cạnh nhau thường có mối quan hệ rất thân thiết với nhau, nên họ thường đi cùng nhau để tạo thành các nhóm nhảy

Ví dụ với dãy số trên sẽ có 6 nhóm nhảy:

Nhóm 1: 5,9     -> độ lệch tối đa = 4
Nhóm 2: 9,7     -> độ lệch tối đa = 2
Nhóm 3: 7,1     -> độ lệch tối đa = 6
Nhóm 4: 5,9,7   -> độ lệch tối đa = 4
Nhóm 5: 9,7,1   -> độ lệch tối đa = 8
Nhóm 6: 5,9,7,1 -> độ lệch tối đa = 8

=> Tổng chênh lệch của tất cả các nhóm nhảy trong dãy số trên là 32

Hãy tìm tổng chênh lệch của tất cả các nhóm nhảy của một dãy số

Giới hạn

30%: \(1< n \le 10^2\)

40%: \(1< n \le 10^3\)

30%: \(1< n \le 10^6\)

\(0 < a_i < 10^6\)

Đầu vào

Dòng đầu chứa một só tự nhiên \(n\) là số lượng số trong dãy số

Dòng tiếp theo gồm \(n\) số tự nhiên \(a_i\) là các con số nằm trong dãy số

Đầu ra

Một số duy nhất là kết quả của bài toán

Ví dụ 1

Đầu vào

4
5 9 7 1

Đầu ra

32

Ví dụ 2

Đầu vào

4
3 4 1 2

Đầu ra

14

Ví dụ 3

Đầu vào

5
4 4 4 4 4

Đầu ra

0

Comments


  • 2
    TICHPX  commented on April 22, 2024, 1:03 p.m.

    xin anh em một bộ test

    //Tichpx
#include<bits/stdc++.h>
using namespace std;
long X[1000006],Y[1000006];
void sol(long n,long *a,int z,int t)
{
    stack<pair<int,int>> A,B;
    A.push({INT_MAX,0});
    B.push({-INT_MAX,0});
    for(int i=1;i<=n;i++)
    {
        while(A.top().first<a[i]) A.pop();
        X[i*z+(n+1-i)*t]*=(i-A.top().second);
        A.push({a[i],i});
        while(B.top().first>a[i]) B.pop();
        Y[i*z+(n+1-i)*t]*=(i-B.top().second);
        B.push({a[i],i});
    }
}
int main()
{
    long n=4,res=0;
    cin>>n;
    long a[n+5] ={0,5,9,7,1};
    fill(X,X+n+1,1);
    fill(Y,Y+n+1,1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sol(n,a,1,0);
    reverse(a+1,a+n+1);
    sol(n,a,0,1);
    for(int i=1;i<=n;i++) res+=(X[i]-Y[i])*a[n+1-i];
    cout<<res;
}