模板
找出最左边的一个，最右边的一个，和长度
注意找左位置时要判断：
1>不可以是字串结尾，不然为0或为空
2>不可以不等于key
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,m; const int N=100003; int d[N]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); int x; while(m--) { scanf("%d",&x); int pos1=lower_bound(d+1,d+n+1,x)-d; if(pos1>n || d[pos1]!=x) { printf("-1 -1 -1 "); continue; } int pos2=upper_bound(d+pos1+1,d+n+1,x)-d; printf("%d %d %d ",pos1,pos2-1,pos2-pos1); } return 0; }
例题1
阿弥陀佛数数游戏
N个数字（N<=500000)，K(K<=500000)个问题,
每个问题询问从L到R中，到底有多少个数字是KEY值？
数据都是int可以存储的
神仙思路：
题目虽然有两个关键字，但是只求第一个关键字相等的情况，所以可以直接sort
sort以后找到相等区间，再去搞第二关键字就好
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,k; const int N=500003; struct node { int v,id; bool operator < (const node & o) const { return v==o.v? id<o.id :v<o.v; } }d[N]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&d[i].v ),d[i].id =i; sort(d+1,d+n+1); int l,r; node t; while(k--) { scanf("%d%d%d",&l,&r,&t.v ); t.id =l; int pos1=lower_bound(d+1,d+n+1,t)-d; if(pos1>n || d[pos1].v !=t.v || d[pos1].id >r) printf("0 "); else { t.id =r; int pos2=upper_bound(d+pos1,d+n+1,t)-d; printf("%d ",pos2-pos1); } } return 0; }
例题2
晒衣服
1>贪心
众所周知，堆比sort快（除了我）
#include<cstdio> #include<cstdlib> #include<queue> using namespace std; priority_queue <int> q; int n,a,b; int main() { scanf("%d%d%d",&n,&a,&b); int x; for(int i=1;i<=n;i++) scanf("%d",&x),q.push(x); int t=0; while(q.top() > a*t) { x=q.top() -b; q.pop() ; t++; q.push(x); } printf("%d ",t); return 0; }
2>二分搜索答案
二分快速确认答案范围
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,a,b; const int N=500000; int d[N+3]; bool check(int tm) { int cnt=tm; for(int i=n;i;i--) { if(d[i]<=tm*a) return true; int t=d[i]-tm*a; int nd=(ceil(t/(b*1.0))); if(nd>cnt) return false; else cnt-=nd; } return true; } int main() { scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++) scanf("%d",&d[i]); sort(d+1,d+n+1); int l=1,r=d[n]/a+1; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d ",l); return 0; }
例题3
穿越七彩虹
小数的二分
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; double h,ed; double x[10],r[10]; struct node { double l,r; bool operator < (const node & o) const { if(l==o.l) return r<o.r; else return l<o.l; } }d[10]; bool check(double ch) { for(int i=1;i<=7;i++) { double tt=sqrt((r[i]+ch)*(r[i]+ch) -h*h); d[i].l =x[i]-tt; d[i].r =x[i]+tt; } sort(d+1,d+8); double rr=d[1].r ; if(d[1].l >0) return false; for(int i=2;i<=7;i++) { if(d[i].l >= rr) return rr>=ed; rr=max(d[i].r ,rr); } return rr>=ed; } int main() { scanf("%lf%lf",&h,&ed); for(int i=1;i<=7;i++) scanf("%lf%lf",&x[i],&r[i]); double l=0,r=ed; int cnt=400; while(r-l>=0.0001 && cnt--) { double mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } printf("%.2lf",l);//四舍五入输出两位小数 return 0; }
例题4
矩形分割
平面上有一个大矩形，其左下角坐标（0，0），右上角坐标（R,R)。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于y轴的直线x=k（k是整数) ，使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。并且，要使得大矩形在直线左边的的面积尽可能大。注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int r,n; const int R=1000003;//注意：我将面积落在偏右节点上 long long cf[R],sum[R];//cf是i项减去i-1项//sum是前i项的面积之和 ，则sum的有效部分是[2,r],第一项面积为0 int main() { scanf("%d%d",&r,&n); int x,y,w,h; while(n--) { scanf("%d%d%d%d",&x,&y,&w,&h); cf[x+1]+=h,cf[x+w+1]-=h; } long long nw=0;//差分序列前i项的和 for(int i=1;i<=r;i++) { nw+=cf[i]; sum[i]=sum[i-1]+nw; } long long mid=sum[r]-(sum[r]>>1); int pos=lower_bound(sum,sum+r+1,mid)-sum; while(pos<r && sum[pos]==sum[pos+1]) pos++; int pos2=upper_bound(sum+1,sum+r+1,mid)-sum; if(pos2 && sum[pos2-1]>=mid) pos2--; //注意：这两段其实是不一样的，第二段中的sum[pos2]虽然一定大于了mid，是最小差值，但是不一定是最后一个最小差值 //再加上一个向后寻找就好了 printf("%d ",pos); return 0; }
例题5
有道搜索框
//注意呀：字符串可以都看作数 //只是比大小是左对齐形式罢了 #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; int n,q; const int N=10003; string s[N],ask; int pos; int main() { cin>>n;//cin和scanf不要混用 for(int i=0;i<n;i++) cin>>s[i]; sort(s,s+n); n=unique(s,s+n)-s;//神仙去重 cin>>q; while(q--) { cin>>ask; int pos1=lower_bound(s,s+n,ask)-s; pos=ask.length() ; ask[pos-1]++; int pos2=lower_bound(s+pos1,s+n,ask)-s; if(pos1==pos2)//神仙判ask是否为s[pos1]的前缀 { ask[pos-1]--; cout<<ask<<endl; } else { for(int i=0;i<8 && pos1+i<pos2;i++) cout<<s[pos1+i]<<" "; cout<<endl; } } return 0; }