[TS 10 Quảng Ninh 2223] – Số dãy con

Link đề:

https://oj.program.edu.vn/problem/ts15_sub

Tóm tắt đề:

Cho dãy A gồm các số nguyên dương \(A_i\), xác định dãy con liên tiếp dài nhất có tổng nằm trong đoạn từ m đến M.

Ví dụ minh họa:

Giải thích hình minh họa:

Dãy số dùng làm ví dụ (nền màu trắng):

3 đoạn thỏa điều kiện đầu tiên gồm: đoạn gồm 2 phần tử đầu tiên được đánh số hiệu là 1 và có tổng là 5 , đoạn gồm 2 phần tử tiếp theo được đánh số hiệu là 2 và có tổng là 6, tương tự với đoạn thứ 3 được đánh số là 3

Tương tự ta xét được các đoạn có 3 và 4 phần tử thỏa điều kiện

Hướng dẫn gợi ý:

Từ hình minh họa ta có thể nhận ra hướng xử lý bài toán cần sử dụng kỹ thuật mảng cộng dồn để tính nhanh được tổng của đoạn các phần tử liên tiếp.

Xét mảng cộng dồn của dãy minh họa như sau:

Ý tưởng chính:

Xét mọi vị trí i từ 1 đến n, ta cần xác định 2 vị trí \( j_{min}\) và \(j_{max}\) thỏa điều kiện:

• Tổng các phần tử từ vị trí i đến vị trí \( j_{min} \ge m \) và Tổng các phần tử từ vị trí i đến vị trí \( j_{max} \le M \)
• Gọi \( res_i \) là số đoạn phần tử liên tiếp thỏa điều kiện bắt đầu từ vị trí i: \( res_i = j_{max} – j_{min} + 1\)

Kết quả bài toán = Tổng tất cả \( res_i \) với \( i \) từ \( 1 \) đến \( n \): \( \sum_{i=1}^{n} res_i \)

Nhận xét để định hướng tối ưu thuật toán:

• Các phần tử trong mảng là số dương nên mảng cộng dồn sẽ là dãy tăng dần (1)
• Áp dụng tìm kiếm nhị phân để xác định vị trí \( j_{min}\) và \(j_{max}\) (2) –> sử dụng lower_bound và upper_bound trong thư viện std của c++

Mã nguồn tham khảo

[author: ThinMienTay]:

Chú ý: trong mã nguồn, ta đặt tương ứng l = a [j_min] (dòng 25) và r = a [j_max] (dòng 26)

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

int main()
{
    long long n,m,M;
    cin>>n>>m>>M; //Nhap so phan tu n, va khoang tong m den M

    vector<long long>a(n);
    for (long long i=0;i<n;i++)
    {
        cin>>a[i]; //Nhap mang a
    }

    //Tao mang prefixsum, prefixsum[i] la tong tu a[0] den a[i-1]
    vector<long long>prefixsum(n+1,0);
    for (long long i=0;i<n;i++)
    {
        prefixsum[i+1]=prefixsum[i]+a[i];
    }

    long long dem=0; //Dem so doan con co tong thuoc [m,M]
    for (long long i=0;i<n;i++)
    {
        long long l=prefixsum[i]+m; //Can tim prefixsum[j] >= prefixsum[i]+m
        long long r=prefixsum[i]+M; //Va prefixsum[j] <= prefixsum[i]+M

        //Tim vi tri dau tien >= l trong doan [i+1, n]
        auto it1=lower_bound(prefixsum.begin()+i+1,prefixsum.end(), l);
        
        //Tim vi tri dau tien > r trong doan [i+1, n]
        auto it2=upper_bound(prefixsum.begin()+i+1,prefixsum.end(),r);

        dem+=it2-it1; //So doan con bat dau tu i thoa man dieu kien
    }

    cout<<dem<<"\n"; //In ket qua
    return 0;
}