NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2016國中組決賽
 B. 兔子

作者 主題: B. 兔子  (閱讀 295 次)

Coding.com

  • 新手
  • *
  • 文章數: 2
    • 檢視個人資料
B. 兔子
« 於: 十一月 27, 2017, 08:18:36 pm »

二分搜
#include<bits/stdc++.h>
using namespace std;
int arr[50];
bool reached[101];
void scream(int a,int i,int n){
   if(a<0){
      return;
   }
   for(int j=i;j<n;j++){
      if((arr[j]-arr)>a){
         scream(a-1,j-1,n);
         return;
      }
      else{
         reached[j]=true;
      }
   }
}
void scream2(int a,int b){
   if(a<0){
      return;
   }
   for(int j=b;j>=0;j--){
      if((arr-arr[j])>a){
         scream2(a-1,j+1);
         return;
      }
      else{
         reached[j]=true;
      }
   }
}
bool check(int a,int b,int n){
   fill(reached,reached+n,false);
   scream2(a,b);
   for(int i=0;i<b;i++){
      if(!reached){
         return false;
      }
   }
   scream(a,b,n);
   for(int i=b;i<n;i++){
      if(!reached){
         return false;
      }
   }
   return true;
}
int bins(int n,int num){
   int l=0,r=101;
   while(l<=r){
      int m=(l+r)/2;
      if(check(m,num,n)){
         r=m;
      }
      else{
         l=m+1;
      }
      if(l>=r){
         break;
      }
   }
   return r;
}
int main(){
   int a;
   cin>>a;
   if(a==1 or a==0){
      cout<<0;
      return 0;
   }
   cin>>arr[0];
   bool s=true;
   for(int i=1;i<a;i++){
      cin>>arr;
      if(arr!=arr[i-1]){
         s=false;
      }
   }
   if(s){
      for(int i=0;i<a;i++){
         cout<<0<<'\n';
      }
      return 0;
   }
   sort(arr,arr+a);
   fill(reached,reached+a,false);
   for(int i=0;i<a;i++){
      cout<<bins(a,i)<<'\n';
   }
}
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2016國中組決賽
 B. 兔子