Trọng số của dãy số

algorithm
c++

(Kirito-kun) #1

Trọng số của một dãy số nguyên a1, a2, . . , an được tính bằng:

  • Hiệu của tổng các số có chỉ số lẻ và tổng các số có chỉ số chẵn

Ta có phép biến đổi dãy số như sau: Xóa đi một số phần tử để nhận được một dãy số mới.3

Yêu cầu: Cho dãy số nguyên a1, a2, . . , an, hãy biến đổi dãy để nhận được dãy số có trọng số nhỏ nhất.

Dữ liệu: Vào từ file văn bản WSEQ0.INP gồm hai dòng:

  • Dòng 1: Chứa số nguyên dương n;
  • Dòng 2: Chứa n số nguyên mô tả a1, a2, . . , an (|ai| ≤ 10^9)

Kết quả: Ghi ra file văn bản WSEQ0.OUT gồm một dòng: Ghi một số là trọng số nhỏ nhất của dãy tìm được.

Ví dụ:

WSEQ0.INP WSEQ0.OUT
3
-1 2 5
-6

Ràng buộc:

  • Subtask 1: 50% số điểm tương ứng với n ≤ 20;
  • Subtask 2: 25% số điểm tương ứng với n ≤ 2000;
  • Subtask 3: 25% số điểm tương ứng với n ≤ 200000;

Mọi người có thể cho em xin thuật toán để full bài này được không ạ? Em cảm ơn !


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?