fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12. const int LOG = 18;  
  13.  
  14. int n; ll S; 
  15. int a[2 * N]; 
  16. ll pref[2 * N]; 
  17. int nxt[LOG][2 * N]; // nxt[k][i] = Vị trí mà ta sẽ nhảy đến nếu bắt đầu từ i và nhảy 2^k bước
  18.  
  19. int main() {
  20. 	ios::sync_with_stdio(false); 
  21. 	cin.tie(nullptr);  	
  22. 	cin >> n >> S; 
  23. 	for (int i = 1; i <= n; i++) {
  24. 		cin >> a[i]; 
  25. 		a[i + n] = a[i]; 
  26. 	}
  27.  
  28. 	for (int i = 1; i <= 2 * n; i++) pref[i] = pref[i - 1] + a[i]; 
  29.  
  30. 	// nxt[0][i] = Vị trí j nhỏ nhất >= i sao cho sum(i..j) > S  
  31. 	// <=> pref[j] - pref[i - 1] > S 
  32. 	// <=> pref[j] > pref[i - 1] + S
  33. 	// Ta có mảng pref tăng nghiêm ngặt vì các phần tử của a đều dương
  34. 	// Do đó ta có thể áp dụng tìm kiếm nhị phân để tìm j 
  35. 	for (int i = 1; i <= 2 * n; i++) {
  36. 		int j = upper_bound(pref + i, pref + 2 * n + 1, pref[i - 1] + S) - pref;  
  37. 		nxt[0][i] = j; 
  38. 	}
  39. 	nxt[0][2 * n + 1] = 2 * n + 1; // tường chắn
  40.  
  41. 	for (int k = 1; k < LOG; k++) {
  42. 		for (int i = 1; i <= 2 * n + 1; i++) {
  43. 			nxt[k][i] = nxt[k - 1][nxt[k - 1][i]]; 
  44. 		}
  45. 	}
  46.  
  47. 	// Giả sử ta chọn điểm xuất phát là i 
  48. 	// => Đoạn cần xét là [cur, last] = [i, i + n - 1] 
  49. 	// Khi đó, (số bước nhảy tối đa có thể nhảy từ cur sao cho không vượt quá vị trí last) + 1 
  50. 	// cũng chính là đáp án ta cần tìm của đoạn đấy
  51. 	int best = INF; 
  52. 	for (int i = 1; i <= n; i++) {
  53. 		int ans = 0;
  54. 		int cur = i, last = i + n - 1;  
  55. 		for (int k = LOG - 1; k >= 0; k--) {
  56. 			if (nxt[k][cur] <= last) {
  57. 				ans += (1 << k);  
  58. 				cur = nxt[k][cur]; 
  59. 			}
  60. 		} 
  61. 		ans = ans + 1; // đoạn còn dư ra
  62. 		best = min(best, ans);  
  63. 	}
  64.  
  65. 	cout << best << '\n'; 
  66. }
Success #stdin #stdout 0.01s 30104KB
comments (?)
stdin
copy 
8 5
2 2 2 1 3 1 2 1
stdout
copy 
3
https://ideone.com/kAcxr7
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
secret

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!