首页 > 代码库 > HDOJ 3486 Interviewe ST RMQ

HDOJ 3486 Interviewe ST RMQ

2024-07-17 15:07:09   213人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3486题意：n个人，有顺序，每个人有自己的能力值。你要从中选m个，分成每段长度[n/m]的小段，如果不能整除，多余的最后那段舍弃。每个小段取能力值最大的那个人。所取的人的能力值之和要大于k，问最少的m是多少。

分析：考虑种种做法，均不可行，然后绕回rmq上。n有20w，虽然st可以o(nlogn)预处理o(1)查询，但是如果枚举m，那么每次查询是m次，最坏可是o(n^2)的复杂度。只好无奈看题解了，结果正解就是这个。。然后加一点点优化就能过。。或者二分，不过二分是错误的，不满足单调性。。

 

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6  7 int n, k, tot, maxi; 8 int d[200100][20]; 9 void init()10 {        11     for (int j = 1; (1 << j) < n; j++){12         int t = (1 << j) - 1;13         for (int i = 0; i+t < n; i++){14             d[i][j] = max(d[i][j-1], d[i+(1<<(j-1))][j-1]);15         }16     }17 }18 inline int rmq(int a, int b)19 {20     int l = int(log(double(b-a+1))/log(2.0));21     return max(d[a][l], d[b+1-(1<<l)][l]);22 }23 /*24 int cal(int len)　　　　　　　　//这样写就错了，比如n=3, m=2，本来应该取2段，这个会取3段，导致答案偏小25 {26     int sum = 0;27     for (int i = 0; i+len-1 < n; i += len){28         int j = i+len-1;29         sum += rmq(i, j);30         if (sum > k) break;31     }32     return sum;33 }34 */35 int main()36 {37     while(scanf("%d %d", &n, &k) && n >= 0 && k >= 0)38     {39         tot = maxi = 0;40         for (int i = 0; i < n; i++){41             scanf("%d", &d[i][0]);42             tot += d[i][0];43             maxi = max(maxi, d[i][0]);44         }45         if (tot <= k){46             puts("-1");47             continue;48         }49         init();50         int ans = n;51         for (int i = max(1, k/maxi); i < n; i++){52             //int tmp = cal(n/i);53             int len = n/i;54             int tmp = 0;55             for (int j = 1; j <= i; j++){56                 tmp += rmq((j-1)*len, j*len-1);57                 if (tmp > k) break;58             }59             if (tmp > k){60                 ans = i;61                 break;62             }63         }64         printf("%d\n", ans);65     }66     return 0;67 }

 


联系
我们