fork download
copy 
  1. // OBersevasi 1 => makin besar nilai h, makin banyak air yang bisa diisi
  2. // Observasi 2 => makin kecil nilai h, makin kecil jumlah air yang bisa diisi
  3.  
  4. // kita mau maksimalin jumlah air atau x unit air
  5. // cari h maksimal yang memenuhi
  6.  
  7. // Kita bisa pakai algoritma searching
  8. // Tepatnya pakai Binary Search
  9.  
  10.  
  11. #include <iostream>
  12. using namespace std;
  13.  
  14. long long t, n, x, a[200003];
  15.  
  16. bool cek(long long h) {
  17. 	long long sum = 0;
  18. 	for(int i =0;i < n;i++) {
  19. 		if(a[i] > h) continue;
  20. 		sum += (h - a[i]);
  21. 	}
  22. 	if(sum <= x) return true;
  23. 	else return false;
  24. }
  25.  
  26. void solve () {
  27. 	cin >> n;
  28. 	for (int i = 0;i < n;i++) {
  29. 		cin >> a[i];
  30. 	}
  31. 	long long l = 0;
  32. 	long long r = 2000000000;
  33. 	long long ans = 0;
  34. 	while(l <= r){
  35.         long long mid = (l + r)/2;
  36.         // jadi kita cek misalkan si mid jadi h
  37.         if(cek(mid)){
  38.             l = mid + 1;
  39.             ans = mid;
  40.         } else {
  41.             r = mid - 1;
  42.         }
  43.     }
  44.     cout << ans << endl;
  45. }
  46.  
  47. int main() {
  48. 	// your code goes here
  49. 	cin >> t;
  50.     while(t--){
  51.         solve();
  52.     }
  53. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4bSlC2
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!