Editorial for Bedao Mini Contest 06 - GIRLS
Submitting an official solution before solving the problem yourself is a bannable offence.
Solution từ
Nhận xét: Đề bài yêu cầu các phần tử được chọn không là liên tiếp nhưng không quan trọng thứ tự ~(i < j)~ thế nên cách tối ưu để chọn là sắp xếp mảng các phân tử tăng dần ~\rightarrow~ Phần tử lớn nhất luôn nằm ở đầu đoạn chọn và phần tử bé nhất luôn nằm ở cuối đoạn chọn.
Qua đó, duy trì một đoạn có độ dài ~[r-N+1, r]~ rồi lấy ~max(sum(r-N+1, r))~ và đoạn duy trì phải thỏa ~a_r - a_{r-N+1} \leq K~. Để tối ưu cách lấy ~sum(r-N+1,r)~ ta có thể sử dụng ~prefix~ ~sum~ để tính trong ~O(1)~.
Solution được đóng góp từ bạn
Ta chỉ cần sắp xếp lại mảng theo giá trị tăng dần, chọn các đoạn ~[l, r]~ gồm ~N~ người và kiểm tra xem đoạn này có thỏa mãn điều kiện ~max(a[l \dots r]) - min(a[l \dots r]) \leq K \Leftrightarrow a[r]-a[l] \leq K~ hay không.
Có thể tính tổng giá trị của một đoạn từ ~l~ đến ~r~ trong ~O(1)~ bằng cách sử dụng mảng cộng dồn.
Mảng cộng dồn được tính theo công thức : ~sum[i] = sum[i-1]+a[i]~ với ~1 \leq i \leq M~ .
Sau khi đã có mảng cộng dồn, tổng giá trị đoạn từ ~l~ đến ~r~ bằng ~sum[r] - sum[l-1]~.
Vậy bài này có thể làm trong ~O(n\ log n)~, trong đó:
~O(n\ log n)~ để sắp xếp
~O(n)~ để dựng mảng cộng dồn
~O(n)~ để duyệt qua các đoạn và cập nhật kết quả
Code mẫu
#include <iostream> #include <stdio.h> #include <vector> #include <cmath> #include <math.h> #include <map> #include <algorithm> #include <set> #include <bitset> #include <queue> #include <cstring> #include <stack> #include <iomanip> #include <assert.h> #define _(x) (1LL<<(x)) #define BIT(x,pos) (((x)>>(pos)) & 1LL) #define turn_all(x) (_(x)-1LL) #define bitCnt(x) __builtin_popcountll(x) #define name "test" #define nameTask "" #define fastIO ios::sync_with_stdio(false); cin.tie(0); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; const int N = 1E6; const ll INF = 1E18; int a[N+9]; int m,n,k; ll p[N+9]; int main() { fastIO cin>>m>>n>>k; for (int i = 1;i <= m; ++i) cin>>a[i]; sort(a+1,a+1+m); for (int i = 1;i <= m; ++i) p[i] = p[i-1] + a[i]; ll S = -INF; for (int i = 1;i <= m; ++i) if (i-n+1 >= 1 && a[i] - a[i-n+1] <= k) S = max(S, p[i] - p[i-n]); cout<<(S == -INF ? -2 : S); }
Comments
Idol SPyofgame tuyệt vời quá 😄