Tối ưu bài toán đếm khoảng màu tăng dần độ sáng dài nhất

Bài tập: Mai là ngày valentine, Chi Chi muốn tặng Goku một món quà, Chi đã đan sẵn một chiếc khăn len được tạo nên bởi n khoảng màu có độ rộng bằng nhau nằm liên tiếp nhau. ai là độ sáng của khoảng màu thứ i. Do Goku chỉ thích chiếc khăn có độ sáng các khoảng màu tăng dần. Vì thế, Chi quyết định sẽ cắt chiếc khăn ra và tặng Goku một đoạn liên tiếp trong chiếc khăn đó. Mặt khắc Chi cũng muốn dãi khăn mình tặng là dài nhất có thể, vì vậy cô ấy đã nhờ bạn tính xem đoạn khăn dài nhất mà cô ấy có thể cắt ra để tặng GOku chứa bao nhiêu khoảng màu?

Dữ liệu:

  • dòng đầu tiên chứa số nguyên dương n (1<=n<=10000000)
  • dòng thứ 2 chứa các số nguyên dương a1,a2,…an (1<=ai<=1000000000)

Dữ liệu ra: kết quả bài toán trên một dòng

viết coder như thế này mà chỉ chạy được 16 test

#include<bits/stdc++.h>
using namespace std;
void nhap(long long a[],long long &n)
{
    cin>>n;
    for(long long i=1;i<=n;i++)
        cin>>a[i];
}
int dem(long long a[],long long n)
{
    int d,maxx;
    maxx=1;
    for(long long i=1;i<n;i++)
    {
        d=1;
       while(a[i]<a[i+1])
       {
           d++;
           i++;
       }
       if(maxx<d)
        maxx=d;
    }
    return maxx;
}
int main()
{
    long long n,a[100000],i;
    
    nhap(a,n);
    cout<<dem(a,n);
   
}

Bạn sửa lại cả hai dấu ~~ thành 3 dấu ``` để sử dụng markdown nha. :slight_smile:

Cách bạn làm có độ phức tạp là O(n^2). Cần giảm xuống O(n) mới pass được hết.

Bạn thử nghĩ xem, ví dụ khoảng tăng dần bắt đầu từ ô màu thứ i có chiều dài là K thì có cần tính lại khoảng màu tăng dần từ ô màu thứ i + 1 nữa không. :slight_smile:

2 Likes

cảm ơn bạn Sherly1001

Nhờ Sherly1001 sửa lại đoạn code của mình

Code của bạn có sai đâu mà sửa. :kissing:
Với lại bạn nên lưu ý array index nó bắt đầu từ 0.

int dem(long long a[],long long n)
{
    int len = 0;
    for (int i = 1, j = 1; j <= n; i = ++j) {
        while (a[j] < a[j + 1]) ++j;
        if (j - i + 1 > len) len = j - i + 1;
    }
    return len;
}
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?