題干：

鏈接：https://ac.nowcoder.com/acm/contest/82/B
來源：牛客網
?

給你一個長為n的序列a和一個常數k

有m次詢問，每次查詢一個區間[l,r]內所有數最少分成多少個連續段，使得每段的和都 <= k

如果這一次查詢無解，輸出"Chtholly"

輸入描述:

第一行三個數n,m,k 第二行n個數表示這個序列a 之后m行，每行給出兩個數l r表示一次詢問

輸出描述:

輸出m行，每行一個整數，表示答案

示例1

輸入

復制

5 5 7 2 3 2 3 4 3 3 4 4 5 5 1 5 2 4

輸出

復制

1 1 1 2 2

備注:

對于100%的數據，1 <= n , m <= 1000000 , 1 <= ai , k <= 1000000000

解題報告：
首先發現可以貪心，這樣是O( nm )的
由于k固定，考慮數組中每個位置i向最大的j+1使得a[i..j]的和<=k連邊。這個連邊的結構是個森林，每次查詢即查詢樹的一條鏈，可以倍增維護。O( nlogn + mlogn )

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e6 + 5; int n,m; ll K,a[MAX],sum[MAX]; int f[MAX][22]; int main() {cin>>n>>m>>K;for(int i = 1; i<=n; i++) scanf("%lld",a+i),sum[i] = sum[i-1] + a[i];for(int i = 1; i<=n; i++) {int pos = upper_bound(sum+i,sum+n+1,sum[i-1]+K) - sum;f[i][0] = pos; }for(int j = 0 ; j<=21; j++) f[n+1][j] = n+1;for(int j = 1; j<=21; j++) {for(int i = 1; i<=n; i++)f[i][j] = f[f[i][j-1]][j-1];}while(m--) {int l,r;scanf("%d%d",&l,&r);int ans = 0;for(int j = 21; j>=0; j--) {if(f[l][j] <= r) ans += (1<<j),l = f[l][j];}if(f[l][0] > r) {printf("%d\n",ans+1);}else printf("Chtholly\n");}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 82B】区间的连续段（贪心，建图，倍增）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。