Day_4

#97. 不太甜的糖果

作为二分与区间和一个引子题，这道题目十分巧妙的运用了二分与区间和算法。先sort排序，使得数组A(输入数组)满足二分算法的二段性，随后使用出区间和快速求一段区间的和，这道题便能迎刃而解，不会因时间复杂度度太高而超时。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
int n,m,ans=N;
int a[N],s[N];
bool ch(int i,int mid){
   int h=s[mid]-s[i-1];
   return h<m;
}
int main(){
   cin>>n>>m;
   for(int i=1;i<=n;i++){
   	cin>>a[i];
   	s[i]=s[i-1]+a[i];
   }	

   for(int i=1;i<=n;i++){
   	int l=i,r=n;
   	while(l<r){
   		int mid=(l+r)/2;
   		if(ch(i,mid)) l=mid+1;
   		else r=mid;
   	}
   	if(s[r]-s[i-1]>=m) ans=min(ans,r-i+1);
   }
   if (ans == (int)3e5) ans = 0;
   cout<<ans;
   return 0;
}

#98. 二分模板题

十分经典的模板题（不经典怎么叫“ 二分模板题”？），想要弄懂二分算法，必须先搞懂这题。

[]

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[100006];
int er_fen1(int l,int r){
   while(l<r){
   	int mid=(l+r)/2;
   	if(a[mid]>=k) r=mid;
   	else l=mid+1;
   }
   return l;
}
int er_fen2(int l,int r){
   while(l<r){
   	int mid=(l+r+1)/2;
   	if(a[mid]<=k) l=mid;
   	else r=mid-1;
   }
   return l;
}
int main(){
   cin>>n>>m;
   for(int i=1;i<=n;i++){
   	cin>>a[i];
   }
   while(m--){
   	cin>>k;
   	int j=er_fen1(1,n);
   	int h=er_fen2(1,n);
   	if(a[j]!=k) cout<<"-1 -1"<<endl;
   	else cout<<j-1<<" "<<h-1<<endl;
   }
   return 0;
}

#T1242. 网线主管

二分分支：三分