HDU3486RMQ+二分

题意

给一组数&＃xff0c;分成M组&＃xff0c;每一组的人数为n/m&＃xff0c;剩下的人丢弃。每组取最大的数&＃xff0c;问要得到严格大于某个数的总和&＃xff0c;最少需要分多少组

题解

这种题分组题&＃xff0c;很容易便能想到是二分。只是注意一些边界情况就可以了&＃xff0c;比如说选取的组位置边界。

注意事项

处理问题不要刻意追求巧妙&＃xff0c;选择最稳妥的方式在大多数时候反而会更好。

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define UP(i,l,h) for(int i&＃61;l;i
#define DOWN(i,h,l) for(int i&＃61;h-1;i>&＃61;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[200010];
int d[200010][20];
int n,m;
void rmq_init() {UP(i,0,n) {d[i][0]&＃61;a[i];}for(int j&＃61;1; (1<for(int i&＃61;0; i&＃43;(1<11],d[i&＃43;(1<<(j-1))][j-1]);}}
}int rmq(int l,int r) {int k&＃61;0;W((1<<(k&＃43;1))<&＃61;r-l&＃43;1) {k&＃43;&＃43;;}return max(d[l][k],d[r-(1<1][k]);
}int main() {W(~scanf("%d%d",&n,&m)) {if(n<0&&m<0)break;MEM(d,0);MEM(a,0);UP(i,0,n) {scanf("%d",&a[i]);}rmq_init();int lt&＃61;1,rt&＃61;n;int ans&＃61;-1;W(lt<&＃61;rt) {int mid&＃61;(lt&＃43;rt)/2;
// cout<int pos&＃61;n/mid;LL sum&＃61;0;for(int i&＃61;0; i1);}
// cout<if(sum>m) {ans&＃61;mid;rt&＃61;mid-1;}else{lt&＃61;mid&＃43;1;}}printf("%d\n",ans);}
}/*
3 499
200 200 100
*/