Thứ Sáu, 6 tháng 11, 2020

Bài toán tìm tổng lớn nhất có ràng buộc khoảng cách nhỏ hơn d

 Đề bài: $\href{https://codeforces.com/contest/580/problem/B}{Đây}$

Tóm tắt: Cho $n$ cặp $(a_i,b_i)$ và một số $d$. Hãy chọn ra một tập con (rời rạc) sao không không tồn tại hai chỉ số $i,j$ thỏa mãn $abs(a_i-a_j)<d$ và $\sum(b_i)$  là lớn nhất.

Lời giải:

+ Sort $n$ cặp trên theo thứ tự tăng dần. Sao đó dùng 2 con trỏ, tìm đoạn con liên tiếp thỏa mãn yêu cầu bài toán trên.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 100005
  4. #define F first
  5. #define S second
  6. pair<int,int> a[N];
  7. long long o,res=-1;
  8. int i,j,l,r,n,m;
  9.  
  10. int main(){
  11. // freopen("input.inp","r",stdin);
  12. // freopen("output.out","w",stdout);
  13. cin>>n>>m;
  14. for(i=0;i<n;++i){
  15. scanf("%d%d",&a[i].F,&a[i].S);
  16. }
  17. sort(a,a+n);
  18. for(l=0;l<n;o-=a[l].S,++l){
  19. while(r<n && abs(a[l].F-a[r].F)<m)o+=a[r].S,++r;
  20. if(o>=res) res=o;
  21. }
  22. cout<<res<<"\n";
  23. }


Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...