Bài tập C++ hay

[trothinhthienduc]

Mình nghĩ bài này khá hay và khó, rất mong được các anh em giúp đỡ về thuật toán.

Ở Mai Châu, người ta trồng loại nếp mới. Đồng bào trồng cây này trên một cánh đồng bậc thang gồm 1≤ N ≤ 5000000 khoảnh liên tiếp nhau. Tuy mang tiếng bậc thang, nhưng các khoảnh này lại có những độ cao (so với mặt nước biển) rất khác nhau. Độ cao của khoảnh thứ i là 1 ≤ ai ≤ 2000000000. Lúa chỉ được trồng trên dãy khoảnh ruộng liên tiếp mà chênh lệch giữa khoảnh ruộng cao nhất và khoảnh ruộng thấp nhất trong dãy có giá trị tối đa là T. Hãy tìm dãy khoảnh ruộng liên tiếp dài nhất thỏa mãn tính chất này.

INPUT
Dòng đầu ghi hai số N và T. Dòng thứ 2 ghi N số ai, lần lượt là độ cao các khoảnh ruộng

OUTPUT
Số lượng khoảnh ruộng liên tiếp lớn nhất có thể trồng lúa.

dữ liệu vào : 9 3
7 3 5 7 10 8 8 11 12

dữ liệu ra: 4

giải thích: Là dãy 7, 10, 8, 8

View more random threads:

• Giúp em làm bài này với..
• Lấy mã phím CTRL,SHIFT....
• Topic : lý thuyết đồ thị
• xuất min khác 0
• Xóa phần tử của mảng
• Nhờ các bác code thêm phần nhập dữ liệu từ file txt vào bài struct sinh viên này
• [ Solved ]Tìm số nguyên tố!!!!
• Bài tập mảng sắp xếp tên theo ABC
• Mọi người xem giúp mình bài này sai ở đâu vậy
• [ Solved ]Các anh pro ơi help em đệ qui

[phongkhamkt1]

Mình cũng mới học C, chưa học thuật toán nhưng cũng xin góp với bạn 1 cách giải hơi thô bạo này:

Tóm tắt đề bài: Cho dãy A: a1, a2, a3, ... an và số t. Tìm số m lớn nhất sao cho tồn tại dãy S: a[k+1], a[k+2], ... a[k+m] có max(S) - min(S) <=t,k>=0 và k+m<=n.
Cách làm: duyệt từ đầu dãy, tại mỗi vị trí tiến hành kiểm tra các phần tử tiếp sau đến khi nào còn thỏa điều kiện (max - min <=t), lưu lại độ dài dãy lớn nhất.

length:=1; //độ dài dãy dài nhất
i := 1; //biến đếm duyệt dãy
while(i<n)
{	
	max := min := a[i];
	temp := 1; //Biến trung gian lưu độ dài dãy đang xét
	for(j := i+1 tới n)
	{
		if(a[j] > max) max: = a[j];
		else if(a[j] <min)min = a[j];
		if((max – min) > t) break;
		temp:=temp+1;
	}	
	if(temp >length) length := temp;
	i:=i+1;
        
}
Xuất kết quả length;

Bạn có thể thêm 1 biến tracking theo dõi vị trí đầu tiên của dãy dài nhất để biết đó là dãy nào. và thêm 1 vài điều kiện để giảm bớt số vòng lặp.

[shipcaptainno1]

5e6 mà O(N^2) là fail oài.

[sala4ever]

#include <iostream>
#include <cstdio>
#include <iostream>
#include <climits>

using namespace std;

#define maxn 5000002

int n,t;
int a[maxn],res;

void input()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}
void solve()
{
    a[0]=INT_MAX;
    a[n+1]=a[0];
    int l,r;
    for(int i=1;i<=n;i++)
    {
        l=i;
        while(a[i]+t>=a[l]&&a[l]>=a[i])
            l--;
        r=i;
        while(a[i]+t>=a[r]&&a[r]>=a[i])
            r++;
        if(r-l-1>res)
            res=r-l-1;
        l=i;
        while(a[i]-t>=a[l]&&a[l]<=a[i])
            l--;
        r=i;
        while(a[i]-t>=a[r]&&a[r]<=a[i])
            r++;
        if(r-l-1>res)
            res=r-l-1;
    }
}
void output()
{
    cout<<res;
}

int main()
{
    freopen("rice.inp","r",stdin);
    freopen("rice.out","w",stdout);
    input();
    solve();
    output();
}

Thuật của mình là O(nlogn) [IMG]images/smilies/smile.png[/IMG]
Mình cần 1 thuật O(n) , mong được các pro giúp đỡ