HDU3486 RMQ

 1 /*多么变态的一道题，交了18次*/
 2 
 3 
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cmath>
 7 #define max(a,b) (a>b?a:b)
 8 int dp[200005][20],llog2[200005];//用llog2数组进行优化
 9 int n,k;
10 
11 void DpMax(){
12     for(int j=1;j<=llog2[n]+1;j++){//llog2
13         for(int i=1;i+(1<<j)-1<=n;i++){
14             dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
15         }
16     }
17 }
18 
19 int GetMax(int L,int R){
20     int j=llog2[R-L+1];//llog2
21     return max(dp[L][j],dp[R-(1<<j)+1][j]);
22 }
23 
24 int work(){
25     int pre_num = -1, pre_tot = -1, pre_sum;
26     for(int i = 1; i <= n; ++i) //分成i组
27     {
28         int num = n / i;    //每组num个
29         int sum = num * i;  //总的多少人
30         int tot = 0;
31         if(num == pre_num)  //如果和前一次一样则从前一次继续累加即可
32         {
33             tot = pre_tot;
34             for(int j = pre_sum + num; j <= sum; j+= num)
35             {
36                 tot += GetMax(j - num + 1, j);
37                 if(tot > k)
38                     return i;
39             }
40             pre_tot = tot;
41             pre_sum = sum;
42         }
43         else
44         {
45             for(int j = num; j <= sum; j += num)
46             {
47                 tot += GetMax(j-num+1, j);
48                 if(tot > k)
49                     return i;
50             }
51             pre_num = num;
52             pre_tot = tot;
53             pre_sum = sum;
54         }
55     }
56     return -1;
57 }
58 
59 int main(){
60     for(int i=2;i<200005;++i){//llog2
61         llog2[i]=(i&(i-1))==0?llog2[i-1]+1:llog2[i-1];
62     }
63     while(scanf("%d%d",&n,&k),n>0||k>0){
64         memset(dp,0,sizeof(dp));
65         for(int i=1;i<=n;i++){
66             scanf("%d",&dp[i][0]);
67         }
68         DpMax();
69         printf("%d
",work());
70     }
71 }
72 
73 
74