Thứ Bảy, 28 tháng 11, 2020

Bài toán lần lượt cộng tổng và tách mảng để được tổng cộng dồn lớn nhất

 Đề bài: $\href{https://codeforces.com/problemset/problem/461/A}{Đây}$

Tóm tắt: Bài toán lần lượt cộng tổng và tách mảng để được tổng cộng dồn lớn nhất 

Lời giải: Ở bài này, ta chỉ cần tham lam là được, và nó có dạng:

1 2 3 4 5

1 2 3 4

1 2 3

1 2

Khi đó ta dễ dàng suy ra được quy luật của bài toán

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll n;
  6. cin>>n;
  7. ll a[n];
  8. ll i;
  9. ll sum=0;
  10. for(i=0;i<n;i++) {cin>>a[i];}
  11. sort(a,a+n);
  12. for(i=0;i<n;i++) sum=sum+a[i]*(i+2);
  13. sum-=a[n-1];
  14. cout<<sum;
  15. return 0;
  16. }

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ự...