Thứ Ba, 10 tháng 11, 2020

Bài toán đốn củi

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

Tóm tắt: Cho n cái cây được đặt tại các vị trí cho trước và chiều cao tương ứng. Một tiều phu khi đốn một cái cây bất kì thì nó sẽ ngã bên trái hoặc bên phải. Biết rằng, điều kiện để đốn được một chiếc cây, là khi chiếc cây được đốn ngã xuống, nó không được đụng bất kì cây bên cạnh nào. Hỏi số cây lớn nhất có thể đốn là bao nhiêu.

Lời giải: Ở bài này, ta sử dụng giải thuật tham lam, cứ duyệt từ trái sang phải, cây nào có thể đốn bên trái thì ta đốn trước, tiếp theo xét tới bên phải, đứng yên,... 

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. // freopen("input.inp","r",stdin);
  6. // freopen("output.out","w",stdout);
  7. ll n;
  8. cin>>n;
  9. ll a[n+1],b[n+1];
  10. ll i;
  11. for(i=0;i<n;i++) cin>>a[i]>>b[i];
  12. a[n]=1000000000000000000;
  13. ll s=1;
  14. for(i=1;i<n;i++){
  15. if(a[i]-a[i-1]>b[i]) s++;
  16. else if(a[i+1]-a[i]>b[i]){
  17. s++;
  18. a[i]+=b[i];
  19. }
  20. }
  21. cout<<s;
  22. return 0;
  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ự...