PTA二分专题(1085-1010-1044-1048)_综合

一、前言：

lower_bound(val): 返回容器中第一个值【大于或等于】val的元素的iterator位置。
upper_bound(val): 返回容器中第一个值【大于】val的元素的iterator位置。

二、题目：

1、1085 Perfect Sequence
分析：题目要求选取满足要求的最长序列。能使选取方案数目最大的一定是该递增序列连续的若干个数。可以用lowwer_bound函数，查找第一个满足条件的位置。
注意点：这里有乘法，需要开longlong，要不最后一个测试点过不了。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 200100
using namespace std;
typedef long long ll;
ll a[maxn];
ll n,p,ans=1;
int main(){
    std::ios::sync_with_stdio(false);cin>>n>>p;for(ll i=0;i<n;i++){
    cin>>a[i];}sort(a,a+n);for(int i=0;i<n;i++){
    ll tmp=a[i]*p;ll cur=upper_bound(a,a+n,tmp)-a;ans=max(ans,cur-i);}cout<<ans<<endl;return 0;
}

2、1010 Radix
分析：先前写过，二分第二个数的进制即可.
https://wangfx.blog.csdn.net/article/details/88652088

3、1044 Shopping in Mars
题意：要求打印出所有和为S的子序列的起点和终点，如果没有和为s的子序列，那么打印出大于和S（大于S最小）的那个子序列的起点和终点。
分析：
先前求出前缀和sum[i]；
然后扫描前缀和sum[i]两遍。第一遍扫描，枚举每一个起点，二分查找大于和为m的终点的位置，从而找到距离m最近的值。第二遍扫描，找到所有距离为刚刚求出来的最近的值。
由于前缀和是严格单调递增的，所以这里lower_bound()和upper_bound是等价的，如果是不减，那么这里

开始的时候，自己的二分是这样写的，一直WA。
这种二分的写法应该是适用于查找一个单调序列中是否存在一个数x，存在就返回坐标。
（1）查找单调序列中是否存在一个元素x的写法

int solve(int l,int r,int i){
    int base=l,top=r,mid;int sumSeq;while(base<=top){
    mid=(base+top)/2;sumSeq=sum[mid]-sum[i-1];if(sumSeq>m){
    top=mid-1;}else if(sumSeq<m){
    base=mid+1;}else{
    break;}}return mid;
}

（2）查找单调序列中，第一个大于x、最后一个小于x的元素的位置（实际上就是实现了lower_bound和upper_bound）的写法。
https://www.cnblogs.com/dilthey/p/9903668.html

得分：25/25
直接用lower_bound()做。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100010
using namespace std;
int n,m;
int a[maxn],sum[maxn];
vector<int> v1,v2;
int main(){
    std::ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){
    cin>>a[i];sum[i]=sum[i-1]+a[i];}//查找距离m最小的值int minn=inf;for(int i=1;i<=n;i++){
    int rr=sum[i-1]+m;int pos=lower_bound(sum,sum+n,rr)-sum;int sumSeq=sum[pos]-sum[i-1];//cout<<"sumSeq "<<sumSeq<<endl; if(sumSeq==m){
    minn=m;break;}else if(sumSeq<minn &&sumSeq>m){
    minn=sumSeq;}//cout<<pos<<endl;} //把所有长度为minn的都存储for(int i=1;i<=n;i++){
    int rr=sum[i-1]+m;int pos=lower_bound(sum,sum+n,rr)-sum;int sumSeq=sum[pos]-sum[i-1];if(sumSeq==minn){
    v1.push_back(i);v2.push_back(pos);}}for(int i=0;i<v1.size();i++){
    cout<<v1[i]<<"-"<<v2[i]<<endl;} return 0;
}

手写lower_bound。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100010
using namespace std;
typedef long long ll;
vector<int> v1,v2;
int a[maxn],sum[maxn];
int m,n,pos;
int main(){
    std::ios::sync_with_stdio(false);memset(a,0,sizeof(a));memset(sum,0,sizeof(sum));cin>>n>>m;for(int i=1;i<=n;i++){
    cin>>a[i];}for(int i=0;i<n;i++){
    sum[i+1]=sum[i]+a[i+1];}int minn=inf;//第一遍扫，求出距离m的最近值是多少for(int i=1;i<=n;i++){
    int base=i,top=n,mid,sumSeq;while(base<top){
    mid=(base+top)/2;sumSeq=sum[mid]-sum[i-1];if(sumSeq>=m){
    top=mid;}else{
    base=mid+1;}}sumSeq=sum[top]-sum[i-1];if(sumSeq==m){
    minn=sumSeq;break;}else if(sumSeq<minn&&sumSeq>m){
    minn=sumSeq;}}for(int i=1;i<=n;i++){
    int base=i,top=n,mid,sumSeq;while(base<top){
    mid=(base+top)/2;sumSeq=sum[mid]-sum[i-1];if(sumSeq>=m){
    top=mid;}else{
    base=mid+1;}}sumSeq=sum[top]-sum[i-1];//cout<<i<<" "<<base<<" "<<sumSeq<<endl;if(sumSeq==minn){
    v1.push_back(i);v2.push_back(base);}}for(int i=0;i<v1.size();i++){
    cout<<v1[i]<<"-"<<v2[i]<<endl;}return 0;
}

4、1048 Find Coins （25 分)
题意分析：查找是否存在一对匹配的a[i]和a[j]，使两者的和为m。
排序，扫描，二分查找是否存在m-a[i]即可。
这里要注意的是，判断的时候要确保 $i! = j$ 。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100010
using namespace std;
int n,m;
int a[maxn];
int solve(int x){
    int l=0,r=n-1,mid;while(l<=r){
    mid=(l+r)/2;if(a[mid]>x){
    r=mid-1;}else if(a[mid]<x){
    l=mid+1;}else{
    return mid;}}return -1;
}
int main(){
    std::ios::sync_with_stdio(false);cin>>n>>m;for(int i=0;i<n;i++){
    cin>>a[i];}sort(a,a+n);bool flag=false;for(int i=0;i<n;i++){
    int num=m-a[i];//二分查找num是否在数列中存在int pos=solve(num);if(pos!=-1 &&i!=pos){
    flag=true;cout<<a[i]<<" "<<a[pos]<<endl;break;}}if(!flag) cout<<"No Solution"<<endl;return 0;
}