Bài tập  /  Bài đang cần trả lời

Hãy chia dãy này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn bằng nhau

viết code C++ hay Pascal đều được
----- Nội dung ảnh -----
Cho dãy số nguyên. Hãy chia dãy này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn bằng nhau.

Dữ liệu:
- Dòng đầu ghi n (n ≤ 100);
- Các dòng tiếp theo ghi a1, a2, ..., an (|ai| ≤ 10^9).

Kết quả:
- Dòng đầu tiên ghi K là số đoạn cần chia;
- Dòng thứ hai ghi K số nguyên là chỉ số cuối cùng của K đoạn theo thứ tự từ trái sang phải. Nếu có nhiều phương án thì in một phương án bất kỳ.

Ví dụ:
Dữ liệu:
6
5 2 3 2 2 1

Kết quả:
3
1 3 6
1 Xem trả lời
Hỏi chi tiết
22
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để chia dãy thành nhiều đoạn sao cho tổng các phần tử trong các đoạn bằng nhau, bạn có thể làm theo các bước sau:

1. **Tính tổng các phần tử**: Đầu tiên, bạn cần tính tổng của toàn bộ dãy số.

2. **Tìm ước số**: Kiểm tra các ước số của tổng. Điều này giúp xác định các tổng mà các đoạn có thể chia thành.

3. **Phân chia dãy**:
- Sử dụng một biến để theo dõi tổng hiện tại.
- Duyệt qua từng phần tử trong dãy, cộng dồn vào tổng hiện tại.
- Khi tổng hiện tại bằng một trong các ước số, bạn sẽ tách đoạn tại điểm đó và reset tổng hiện tại về 0.

4. **Kết quả**: Ghi lại số lượng đoạn và các đoạn đã được tách.

### Ví dụ cụ thể

Dữ liệu đầu vào: `6, 5, 2, 3, 2, 2, 1`

- **Tổng**: \( 6 + 5 + 2 + 3 + 2 + 2 + 1 = 21 \)
- **Ước số**: Có thể chia thành các đoạn có tổng là 1, 3, 7, 21.

Giả sử bạn chọn tổng cho mỗi đoạn là 7:
- Đoạn 1: `6, 1` (tổng = 7)
- Đoạn 2: `5, 2` (tổng = 7)
- Đoạn 3: `3, 2, 2` (tổng = 7)

Kết quả sẽ là 3 đoạn, và bạn sẽ ghi lại kết quả trong định dạng yêu cầu.

### Kết luận
Áp dụng quy trình này cho dãy số đã cho để tìm ra số đoạn lớn nhất với tổng các phần tử bằng nhau.
1
1
Avicii
04/01 09:02:12
+5đ tặng
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

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

    long long total_sum = accumulate(a.begin(), a.end(), 0LL);

    int max_segments = 0;
    vector<int> result;

    for (int k = 1; k <= n; ++k) {
        if (total_sum % k == 0) {
            long long target_sum = total_sum / k;
            int current_sum = 0;
            int segments = 0;
            vector<int> current_result;
            for (int i = 0; i < n; ++i) {
                current_sum += a[i];
                if (current_sum == target_sum) {
                    segments++;
                    current_result.push_back(i + 1);
                    current_sum = 0;
                } else if (current_sum > target_sum) {
                    segments = 0;
                    break; // Không thể chia theo ước số này
                }
            }
            if (segments == k && segments > max_segments) {
                max_segments = segments;
                result = current_result;
            }
        }
    }

    if (max_segments == 0) {
        cout << 1 << endl;
        cout << n << endl;
    } else {
        cout << max_segments << endl;
        for (int i = 0; i < result.size(); ++i) {
            cout << result[i] << (i == result.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường
×
Trợ lý ảo Trợ lý ảo
Gửi câu hỏi
×