题意
给一组数,分成M组,每一组的人数为n/m,剩下的人丢弃。每组取最大的数,问要得到严格大于某个数的总和,最少需要分多少组
题解
这种题分组题,很容易便能想到是二分。只是注意一些边界情况就可以了,比如说选取的组位置边界。
注意事项
处理问题不要刻意追求巧妙,选择最稳妥的方式在大多数时候反而会更好。
代码
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<string>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 800010
#define MOD 1000000007
#define EPS 1e-3
using namespace std;
int a[];
int d[][];
int n,m;
void rmq_init() {
UP(i,,n) {
d[i][]=a[i];
}
for(int j=; (<<j)<=n; j++) {
for(int i=; i+(<<j)-<n; i++) {
d[i][j]=max(d[i][j-],d[i+(<<(j-))][j-]);
}
}
}
int rmq(int l,int r) {
int k=;
W((<<(k+))<=r-l+) {
k++;
}
return max(d[l][k],d[r-(<<k)+][k]);
}
int main() {
W(~scanf("%d%d",&n,&m)) {
if(n<&&m<)
break;
MEM(d,);
MEM(a,);
UP(i,,n) {
scanf("%d",&a[i]);
}
rmq_init();
int lt=,rt=n;
int ans=-;
W(lt<=rt) {
int mid=(lt+rt)/;
// cout<<lt<<" "<<rt<<endl;
int pos=n/mid;
LL sum=;
for(int i=; i<pos*mid; i+=pos) {
sum+=rmq(i,i+pos-);
}
// cout<<sum<<" "<<mid<<" "<<pos<<endl;
if(sum>m) {
ans=mid;
rt=mid-;
}else{
lt=mid+;
}
}
printf("%d\n",ans);
}
}
/*
3 499
200 200 100
*/