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