HDU 3486 Interviewe - Qiuqiqiu - 博客园

原题链接:Interviewe(hdoj/hdu3486) ?
文章价值(3) ?
阅读数(155) ?

?

?

?

http://acm.hdu.edu.cn/showproblem.php?pid=3486

RMQ

知道二分是错的,写了个加简单优化的枚举还是超时,只能用错误的二分

做这题主要为了学习RMQ,别的细节就不管了

View Code
 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 const int N=200010, A=1001;
 7 int a[N];
 8 int n,k;
 9 int st[N][20],lg2[N];
10 void ST(int *a,int n)
11 {
12     lg2[0]=-1;
13     for(int i=1;i<=n;i++)
14         lg2[i]=lg2[i-1]+(i&(i-1)?0:1);
15     for(int i=0;i0]=a[i];
16     for(int j=1;j<=lg2[n];j++)
17         for(int i=0;lg2[n-i]>=j;i++)
18             st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
19 }
20 int RMQ(int x,int y)
21 {
22     int k=lg2[y-x+1];
23     return max(st[x][k],st[y-(1<<>1][k]);
24 }
25 bool ok(int c)
26 {
27     int t=n/c, s=0;
28     for(int i=0;i1);
29     return s>k;
30 }
31 int main()
32 {
33     while(scanf("%d%d",&n,&k),n>=0 || k>=0)
34     {
35         int s=0;
36         for(int i=0;i<>)
37         {
38             scanf("%d",&a[i]);
39             s+=a[i];
40         }
41         if(s<=k) {printf("-1\n"); continue;}
42         ST(a,n);
43         int l=1, r=n;
44         while(l<r)
45         {
46             int m=(l+r)/2;
47             if(ok(m)) r=m;
48             else l=m+1;
49         }
50         printf("%d\n",l);
51     }
52     return 0;
53 }
posted on 2012-05-08 17:05 Qiuqiqiu 阅读(...) 评论(...) 编辑 收藏




(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: