首页 > 代码库 > ZOJ 3726 RMQ + 二分
ZOJ 3726 RMQ + 二分
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5072
区域赛果然无水题
通过率最高的一道题 以为二分下就OK 然后WA了果断 外加int没用long long WA
好久没用RMQ 调试也花了一点时间,
upper——bound返回的是大于x的第一个数的下标,最大当然是返回end的位置,注意判断下
注意一点,假设需要打印的张数为x s[i]=<x<s[i+1] 其实 要找的是ans=min(p[i]*x,s[i+1]*p[i+1],s[i+1]*p[i+2]...s[n]*p[n]),所以单单二分必然不行啊
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <cmath> using namespace std; const int MAXN = 1e5+100; #define IN(s) freopen(s,"r",stdin) #define ll long long #define ull unsigned long long const ll INF = ((ull)(-1))>>1; ll s[MAXN],p[MAXN],tot[MAXN]; int n,m; ll d[20]; ll st[MAXN][20]; void init() { for(int i=0;i<n;i++)st[i][0]=tot[i+1]; int k = (int)( log(double(n*1.0)/log(2.0)) ) +1; for(int j=1;j<k;j++) for(int i=0;i<n;i++) { if(i + d[j-1]-1 <n) { st[i][j] = min( st[i][j-1], st[i+d[j-1]][j-1] ); } else break; } } void query(int q) { int y=n-1; for(int i=0;i<q;i++) { int x,k; scanf("%d",&x); int id= upper_bound(s+1,s+1+n,x)-(s+1); if(id>=n) { printf("%lld\n",p[n]*x); continue; } ll ans=INF; ans=min(ans,p[id]*x); k=int( log(double(y-id+1)/log(2.0)) ); ans=min(ans,min(st[id][k],st[y-d[k]+1][k])); printf("%lld\n",ans); } } int main() { //IN("zoj3726.txt"); d[0]=1; for(int i=1;i<21;i++)d[i]=2*d[i-1]; int ncase; scanf("%d",&ncase); while(ncase--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld%lld",&s[i],&p[i]); tot[i]=s[i]*p[i]; } init(); query(m); } return 0; }
ZOJ 3726 RMQ + 二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。