做旅游网站的工作流程图,商城类网站怎么推广,佛山专业网站建设公司推荐,闵行区做网站题意#xff1a; 将\(n\)个数分成\(m\)段相邻区间#xff0c;每段区间的长度为\(\left \lfloor \frac{n}{m} \right \rfloor\)#xff0c;从每段区间选一个最大值#xff0c;要让所有的最大值之和大于\(k\)。求最小的\(m\)。 分析#xff1a; 预处理RMQ#xff0c;维护区…题意 将\(n\)个数分成\(m\)段相邻区间每段区间的长度为\(\left \lfloor \frac{n}{m} \right \rfloor\)从每段区间选一个最大值要让所有的最大值之和大于\(k\)。求最小的\(m\)。 分析 预处理RMQ维护区间最大值。 然后二分\(m\)将每段区间最大值加起来判断即可。 #include cstdio
#include cstring
#include algorithm
using namespace std;const int maxn 200000 10;
const int logmaxn 20;int n, k;
int a[maxn], d[maxn][logmaxn];void init() {for(int i 0; i n; i) d[i][0] a[i];for(int j 1; (1j) n; j)for(int i 0; i (1j) - 1 n; i)d[i][j] max(d[i][j-1], d[i(1(j-1))][j-1]);
}int query(int L, int R) {int k 0;while((1(k1)) R-L1) k;return max(d[L][k], d[R-(1k)1][k]);
}bool check(int x) {int l n / x;int tot 0;for(int i 0; i x; i) {tot query(i * l, (i1) * l - 1);if(tot k) return true;}return false;
}int main()
{while(scanf(%d%d, n, k) 2) {if(n 0 k 0) break;int sum 0, Max 0;for(int i 0; i n; i) {scanf(%d, a i);sum a[i];Max max(Max, a[i]);}if(Max k) { printf(1\n); continue; }if(sum k) { printf(-1\n); continue; }init();int ans n, L 1, R n;while(L R) {int mid (L R) / 2;if(!check(mid)) L mid 1;else R mid;}printf(%d\n, L);}return 0;
} 转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4999399.html
