Code tìm đoạn liên tiếp dài nhất có tổng dương bị sai

Nguyen_Binh_An1 · August 24, 2019, 10:19am

dưới là phần code của e và đề bài, với độ phức tạp O(n), nhưng kết quả chưa chính xác lắm, e nghĩ hướng đi là đúng,

#include <bits/stdc++.h>
using namespace std;
const int LIM = 60009;
int n;
int a[LIM], s[LIM];
void nhapmang()
{
	cin >> n;
	a[0] = 0;
	s[0] = 0;

	for (int i=1; i<=n; i++)
        {
		cin >> a[i];
		s[i] = s[i-1] + a[i];
	}
}

void process()
 {
	int l=0, r=0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++)
			if (s[i] > s[j-1]) {
				if (r-l < i-j) {
					r = i;
					l = j;
				}
				break;
			}
	}
	cout << l << " " << r << endl;
}

int main()
{
    //freopen("PS.inp", "r", stdin);
	//freopen("PS.out", "w", stdout);
	nhapmang();
	process();
}

noname00 · August 24, 2019, 1:59am

Vui lòng up code dưới dạng văn bản lên DNH theo hướng dẫn ở link

tcm · August 24, 2019, 11:23am

Trong phòng thi cứ nghĩ như này là cuộc đời thăng hoa mất
Mình ko biết thuật bạn như nào nhưng liếc qua là O(n^2) rồi. Thuật O(nlogn) như sau:
Gọi ps[i] là tổng tiền tố từ 1 đến i. Để tìm 1 đoạn con L..R có tổng dương, điều kiện là ps[R] - ps[L - 1] > 0, và độ dài dài nhất. Bạn tạo 1 mảng pair mới có first là các phần tử ban đầu của mảng ps, second là các vị trí của nó. Sort theo first, duyệt từng vị trí i, lúc này bài toán trở thành tìm vị trí j trước i sao cho i - j lớn nhất (tức j nhỏ nhất) mà tổng dương.

rogp10 · August 24, 2019, 1:06pm

Hoặc sử dụng mảng con trỏ để swap nhanh còn lại thì so sánh con trỏ thôi.

tcm · August 24, 2019, 1:10pm

Hmm cụ thể là như nào anh nhỉ? em chưa biết thuật đó :v

rogp10 · August 24, 2019, 1:46pm

Phép trừ hay so sánh không bằng hai con trỏ cùng kiểu được định nghĩa khi chúng trỏ vào cùng một vùng nhớ đã cấp phát (động hoặc tĩnh) hoặc một ô đằng sau vùng nhớ chung đó. Nhưng hai con trỏ void* không trừ được vì đã là void thì không biết nó mấy byte

Nghĩa là

#include <iostream>

int a[10][10];

int main() {
   auto p = a[5], q = a[6];
   std::cout << q - p; // vẫn okie
}

Nguyen_Binh_An1 · August 25, 2019, 8:35am

bạn giải thích rõ hơn đc ko

Nguyen_Binh_An1 · August 25, 2019, 8:36am

vậy thuật toán của e là sai ạ

tcm · August 25, 2019, 3:19pm

Kết quả sai thì 99% thuật sai

noname00 · August 25, 2019, 3:24pm

Cứ 2 vòng for n này thì rõ ràng là O(n^2) rồi, làm sao là O(n) được nữa.

rogp10 · August 27, 2019, 1:47pm

Ý là quá lâu đó

Đến đây bài trở thành tìm hai phần tử cách xa nhau nhất mà số đứng trước < số đứng sau. Sau khi có được mảng prefix_sum[0..n] rồi (trừ prefix_sum[0] = 0) thì ta tính best_sum[] theo chiều ngược lại (!) hay nói cách khác, mảng không gỉam từ phải qua trái.

Showtime! Ta gán beg, en = 0, 1 vì đương nhiên a[0] == a[0]. Giờ nếu prefix_sum[beg] >= best_sum[en] thì beg += 1 tức là không còn phù hợp nữa do đằng sau toàn là phần tử bé hơn nó. en += 1 luôn được chạy vì khi tăng chỉ số đầu dãy mà không tăng chỉ số cuối dãy thì dãy không thể dài hơn dãy vừa tìm rồi.

Vậy thì nó ntn

# pseudo!
with f = File.open("PS.INP", READ || MODE_TEXT) do
   n = f.nextInt();
   prefix_sum = [0].reserve(n+1);
   while num = f.nextInt() do
      prefix_sum.append(prefix_sum[-1] + num);
   end
end

best_sum = Array.new(n+1);
best_sum[-1] = prefix_sum[-1];
for i = n-1 to 1 step -1 do
  best_sum[i] = max(best_sum[i+1], prefix_sum[i+1]);
end
beg, beg_max, en = 0,-1,-1;
for i = 1 to n do
 if best_sum[i] >= prefix_sum[beg]
   beg_max, en = beg, i if i - beg > en - beg_max;
   beg += 1;
 end
end

Sherly1001 · August 26, 2019, 4:29pm

Cách của @rogp10 nii khá ổn rồi mà viết bằng Ruby.

Mò lại trong kho thì thấy cách này của kaze neee cũng tương tự nè.