本文主要是介绍HDU 4791二分+线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
13长沙现场赛水题
二分+线段树
二分出页数的所在位置
线段树查找后面区间最小值
#include "stdio.h"
#include "string.h"
#include "math.h"
#include "stdlib.h"struct comp
{int l,r,mid;__int64 min;
} data[400100];__int64 a[100100],b[100100];
__int64 min(__int64 a,__int64 b)
{if (a<b) return a;else return b;
}void build(int l,int r,int k)
{data[k].l=l;data[k].r=r;data[k].mid=(l+r)/2;if (l==r){data[k].min=a[l]*b[l];return ;}build(l,data[k].mid,k*2);build(data[k].mid+1,r,k*2+1);data[k].min=min(data[k*2].min,data[k*2+1].min);
}__int64 search(int l,int r,int k)
{if (data[k].l==l && data[k].r==r)return data[k].min;if (r<=data[k].mid) return search(l,r,k*2);else if (l>data[k].mid) return search(l,r,k*2+1);else return min(search(l,data[k].mid,k*2),search(data[k].mid+1,r,k*2+1));
}int main()
{int t,n,m,ll,i,rr,mid,mark;__int64 x,ans;scanf("%d",&t);while (t--){scanf("%d%d",&n,&m);for (i=1;i<=n;i++)scanf("%I64d%I64d",&a[i],&b[i]);build(1,n,1);while (m--){scanf("%I64d",&x);if (x==0){printf("0\n");continue;}ll=1; rr=n;while (ll<=rr){mid=(ll+rr)/2;if (x>a[mid]) { mark=mid; ll=mid+1;}else rr=mid-1;}ans=x*b[mark];if (mark+1<=n) {x=search(mark+1,n,1);if (x<ans) ans=x;}printf("%I64d\n",ans);}}return 0;
}
这篇关于HDU 4791二分+线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
