1_11

辽宁师范大学 • 张大为@https://daweizh.github.io/noip/

1.11 编程基础之二分查找(10)

查找最接近的元素，http://noi.openjudge.cn/ch0111/01/[+]

#include <iostream>
#include <cstdlib>
using namespace std;

int a[100005],n,m,tmp;

int bfind(int v){
    int l=0,r=n-1,mid;
    
    while(l<=r){
        mid = (l+r) >> 1;
        if(v<=a[mid])
            r = mid-1;
        else
            l = mid+1;
    }
    
    return abs(a[l]-v)<abs(a[r]-v)?a[l]:a[r];
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    cin >> m;
    for(int i=0;i<m;i++){
        cin >> tmp;
        if(tmp<a[0]){
          cout << a[0] << endl;
          continue;
    }
    if(tmp>a[n-1]){
      cout << a[n-1] << endl;
      continue;
    }
        cout << bfind(tmp) << endl;
    }
    
    return 0;
}

二分法求函数的零点，http://noi.openjudge.cn/ch0111/02/[+]

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

double f(double x){
  double ans = pow(x,5.0);
  ans = ans - 15*pow(x,4.0);
  ans = ans + 85*pow(x,3.0);
  ans = ans - 225*pow(x,2.0);
  ans = ans + 274*x;
  ans = ans - 121;
  return ans;
}

int main(){
  double l = 1.5,r = 2.4,mid,ans = 0.0;

  while(l<r){
    mid = (l+r)/2.000000;
    ans = f(mid);	
    if(ans >0.0)
            l = mid;
        else if (ans < 0.0)
            r = mid;
        if (abs(ans-0.000000)<0.00000001)
          break;
  }
  //cout << fixed << setprecision(6) << mid <<  endl;
  printf("%.6f",mid);
  
    return 0;
}

矩形分割，http://noi.openjudge.cn/ch0111/03/[+]

#include <iostream>
#include <cmath>
using namespace std;

long long  r,n,lb,rb,mid,mx;
struct ract{
  long left;
  long top;
  long width;
  long height;
  long long area;
  long long rx;
}rc[10005];

long long judge(int d){
  long long al=0,ar=0;
  for(int i=0;i<n;i++){
    if(rc[i].left<d){
      if(rc[i].rx<=d)
        al = al + rc[i].area;
      else{
        al = al + rc[i].height*(d-rc[i].left);
        ar = ar + rc[i].height*(rc[i].rx-d);
      }
    }else{
      ar = ar+ rc[i].area;
    }
  }
  return al-ar;
}

int main(){
  cin >> r >> n;
  for(int i=0;i<n;i++){
    scanf("%d%d%d%d",&rc[i].left,&rc[i].top,&rc[i].width,&rc[i].height);
    rc[i].rx = rc[i].left + rc[i].width;
    rc[i].area = rc[i].height * rc[i].width;
    mx = max(rc[i].rx,mx);
  }
  
  lb=0;
  rb=r;
  while(lb+1<rb){
    mid = (lb+rb)/2;
    if(judge(mid)>0)
      rb = mid;
    else
      lb = mid;
  }
  
  long long tl = judge(lb);
  long long tr = judge(rb);
  long long ans ;
  
    if( tl<tr){
    if(tl>=0) ans=lb;
    else ans=rb;
  }else if(tl>tr){
    if(tr>=0) ans=rb;
    else ans=lb;
  } else ans=rb;
  if(ans==mx) ans=r;
  printf("%lld\n",ans);		
  return 0;
}

网线主管，http://noi.openjudge.cn/ch0111/04/[+]

#include <iostream>
using namespace std;

double x;
int n,k,a[10005],l,r,mid,mx;

int div(int d){
  int cnt =0;
  for(int i=0;i<n;i++){
    cnt += a[i]/d;
  }
  return cnt;
}

int main(){
  cin >> n >> k;
  for(int i=0;i<n;i++){
    cin >> x;
    a[i]=x*100;
    mx = max(mx,a[i]);
  }
  
  l = 0;
  r = mx+100;
  while(l+1<r){
    mid=(l+r)/2;
    if(div(mid)>=k)
      l = mid;
    else
      r = mid;
  }
  printf("%.2lf\n",l/100.00);
  
  return 0;
}

派，http://noi.openjudge.cn/ch0111/05/[+]

#include <iostream>
#include <cmath>
using namespace std;

int n,f;
double a[10005],mx=0.0,l,r,mid,x;
const double pi=3.141592653589793;//3.141592653578979;

int div(double v){
  int cnt = 0;
  for(int i=0;i<n;i++){
    int t = int(1.0*a[i]/v);
    cnt = cnt + t;
  }
  return cnt;
}

int main(){
  cin >> n >> f;
  for(int i=0;i<n;i++){
    cin >> x;
    a[i]=pi*x*x;
    if(a[i]>mx) mx = a[i];
  }
  r = mx;
  l = 0;
  while(fabs(r-l)>1e-6){
    mid=(l+r)/2;
    if(div(mid)>=(f+1))
      l = mid;
    else
      r = mid;
  }
  
  printf("%.3f\n",l);

  return 0;
}

月度开销，http://noi.openjudge.cn/ch0111/06/[+]

#include <iostream>
using namespace std;

int n,m,a[100005],l,r,mx=0,tt=0,mid;

int judge(int x){
  int sum=0,cnt=0;
  for(int i=0;i<n;i++){
    if(sum+a[i]>x){
      sum = a[i];
      cnt++;
    }else{
      sum = sum + a[i];
    }
  }
  return cnt;
}

int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]>mx) mx = a[i];
    tt = tt + a[i];
  }
  
  l = mx;
  r = tt;
  while(l<=r){
    mid = (l+r)/2;
    if(judge(mid)<m){
      r=mid-1;
    }else{
      l=mid+1;
    }
  }
  cout << mid << endl; 

  return 0;
}

和为给定数，http://noi.openjudge.cn/ch0111/07/[+]

#include <iostream>
#include <algorithm>
using namespace std;

long long n,a[100005],m;

bool fnd(int b,long long x){
  int l=b,r=n;
  while(l<=r){
    int mid = (r+l)/2;
    if(a[mid]==x)
      return true;
    else if(a[mid] < x)
      l=mid+1;
    else
      r = mid-1;
  }
  return false;
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++)
    cin >> a[i];
  sort(a,a+n);
  
  cin >> m;
  int bnd = m/2,flag=1;
  for(int i=0;a[i]<=bnd;i++){
    if(fnd(i+1,m-a[i])){
      flag = 0;
      cout << a[i] << " " << m-a[i]<< endl;
      break;
    }
  }
  
  if(flag) 	
    cout << "No" << endl;

  return 0;
}

不重复地输出数，http://noi.openjudge.cn/ch0111/08/[+]

#include <iostream>
#include <set>
using namespace std;

set<int> a;
int n,x;

int main(){
  cin >> n;
  
  for(int i=0;i<n;i++){
    cin >> x;
    a.insert(x);
  }
  
  for(set<int>::iterator it=a.begin();it!=a.end();it++)
    cout << *it << " ";
  cout << endl;

  return 0;
}

膨胀的木棍，http://noi.openjudge.cn/ch0111/09/[+]

#include <iostream>
#include <cmath>
using namespace std;

double l,c,r,A,lft,rgt,mid;

int main(){
  cin >> l >> c >> r;
  if(l<1e-14){
    cout << "0.000" << endl;
    return 0;
  }
    
  A = l*(1+r*c);
  lft = 0.00;
  rgt = asin(1.0);
  while(rgt-lft>1e-14){
    mid = (lft+rgt)/2;
    if(A*sin(mid)/mid<=l)
      rgt = mid;
    else
      lft = mid;
  }
  
  printf("%.3lf\n",l/2*tan(lft/2));
  
  return 0;
}

河中跳房子，http://noi.openjudge.cn/ch0111/10/[+]

#include <iostream>
using namespace std;

int l,n,m,stn[50005],lb,rb,mid,mm=2000000000;

bool judge(int d){
  int cnt=0,p=0;
  
  for(int i=1;i<=n;i++){
    if(stn[i]-stn[p]<=d)
      cnt++;
    else
      p = i;
    if(cnt>m)
      return true;
  }
  return false;
}

int main(){
  
  cin >> l >> n >> m;
  stn[0]=0;
  for(int i=1;i<=n;i++)
    cin >> stn[i];
  stn[++n]=l;
  lb=0;
  rb=l;
  while(lb<=rb){
    mid=(lb+rb)/2;
    if(judge(mid))
      rb = mid-1;
    else
      lb = mid+1;
  }
  
  cout << lb << endl;
  
  return 0;
}

参考网址

http://noi.openjudge.cn