Two point, three point, 01 point plan [bullet I]

Catalog

One 、 Two points

1. Understanding of different boards

Example 1 ：

Super classic dichotomy ！！！Drying !

---

One 、 Two points

1. Understanding of different boards

【 It is said that dichotomy is easy to write crooked , Pay attention to the details , The next few ways to write , Suggestion is Choose one you are familiar with and write only this , So as not to be confused , However, it is still necessary to understand 】

  want avoid “ Dead cycle ” Appearance , Namely Make every execution change , Instead of judging, it's equivalent to doing nothing , Specifically, the code is l and r To move , Then why is there an endless cycle ？ Because of our mid = ( l + r )/2 yes “ to be divisible by ” ah , yes “ Rounding down ”, When r==l+1 when ,mid Will be equal to the smaller one , That is to say l At this time, if the code on the left is also written   mid = ( l + r )/2 , Then there will be l = mid This is a dead circle （ hold l The assignment is l , What did you do .）【 You can take a series 3 3 3 Do a simulation 】 About the final answer ： Find the equal sign , Last executed mid Namely x The subscript of , Then on the left is r , On the right is l.

Let's look at a kind of writing ： Give up directly mid , Don't think so much , Every time l = mid + 1 , r = mid - 1 , Then the interval must be shrinking ：

Attention! ！ here while Equal sign in the condition of

 

  that , We The final answer What to write , Look at the equal sign , For the code on the left of the above figure ,if ( a[mid]>= x) r = mid - 1 ; Final mid Yes, the answer therefore What we output is r + 1, Or you can look at the following sentence ,a[mid] < x when , l = mid +1 , This is the last time mid Less than x , That's better than x Small 1, So the answer is l , On the right l - 1 , perhaps r. 

And that is ,(l+r) There is a safer way to write Prevent overflow Of ：l + (r-l)/2 ;

 lower_bound It's looking for Greater than or equal to x The position of the first number of ,upper_bound It can be used to find Greater than x The first number of , Remember to subtract the array name （ Because the iterator is returned （ Like a pointer ）, Subtract the array name （ The first address ） You get the subscript ）..

【 above   Even if the sorting subscript is from 1 Start , Don't subtract one more ... Because you subtract the address to get your current subscript , It started with more , Naturally, there is no need to reduce ..】

Example 1 ：

A-[USACO 2009 Dec S]Music Notes_

The question ： Cows knock in turn （ Play ）n A note , Give each note separately （ continuity ） How long do you play ,Q Time to ask , Each time you ask, give a T, ask T~T+1 Which sound do time bulls want to hit .

Ideas ： A prefix and , Then standard dichotomy , You don't have to write it yourself , Just use ready-made functions .

AC Code ：

#include<iostream>
#include<algorithm>
using namespace std;
const int M=5e4+6;
int n,q,a[M];
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	int i,x,t;
	for(i=1;i<=n;i++){
		cin>>x;
		a[i]=a[i-1]+x;
	}
	while(q--){
		cin>>t;
		cout<<upper_bound(a+1,a+1+n,t)-a<<'\n';
	}
	return 0;
}

Super classic Dichotomy ！！！Drying !

Drying - POJ 3104 - Virtual Judge (vjudge.net)

The question ： Yes n Clothes , Each garment contains a certain amount of moisture , There are two ways of natural drying and blowing with a hair dryer , Drying is to reduce one unit of water per minute , Hair dryer is to reduce it every minute k Share water （ You can only blow one thing a minute , You can't change another clothes to blow , The moisture in clothes becomes 0 There will be no change after ） Ask how many minutes at least you can dry all your clothes .

Ideas ： This question satisfies monotonicity , That's two points , hypothesis x Time is the answer , So bigger than the answer （ The judgment is "mid" Time ）, The calculated time will be longer than you expected mid Less （ That is, there is time left , So our answer is big , It should shrink , Shift the right boundary of the interval to the left , vice versa ）

Although here k It contains naturally dried water （ That is, what I did during this period is k No k+1） But be sure to note that the exception here is (k-1),www Why? , Let's just say that everything is a formula Many benefits Be clear at a glance , Don't take it for granted .-> Set the total time as x , t For hair dryer time ,kt + (x-t) >=a[i]  , kt-t >= a[i]-x , (k-1)t >=a[i]

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=1e5+6;
ll n, k, a[M], sum;
bool check(int x){
	int i=upper_bound(a+1,a+1+n,x)-a;// Find the first place to use a hair dryer  
	sum=0;
	for(;i<=n;i++)sum+=(a[i]-x+k-2)/(k-1);// Add one k-2 It's to round up , It can also be used. ceil function  
	return sum<=x?1:0;// The calculation time is smaller than the set , Just go back to real  
}
int main(){
	scanf("%lld",&n);//POJ card cin.... 
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	sort(a+1,a+1+n);
	scanf("%lld",&k);
	if(k==1){printf("%lld",a[n]);return 0;}
	int l=1, r=1e9;
	while(l<r){// One of the two boards , If you are not familiar with it, just look at the above  
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d",r);
	return 0;
}