2022/1/12 差分/二分

校门外的树

差分模板题

#include
using namespace std;
const int N=1e4+10;
int a[N],b[N];
void insert(int l,int r,int c)
{
	b[l]+=c;
	b[r+1]-=c;
}
int main()
{
	int L,n;
	cin>>L>>n;
	
	//每个点都有一棵树 
	for(int i=1;i<=L+1;i++)//下标从一开始 
		a[i]=1;
	
	for(int i=1;i<=L+1;i++)
		b[i]=a[i]-a[i-1];
	
	while(n--)
	{
		int l,r;
		cin>>l>>r;
		l++,r++;//转化成从1开始
		insert(l,r,-1); 
	}
	//求出原数组 
	for(int i=1;i<=L+1;i++)
		a[i]=a[i-1]+b[i];
	
	//因为可能有重复区间，所以可能会出现某点的数量为负
	//把数量为负的变为0; 
	for(int i=1;i<=L+1;i++)
		a[i]=max(0,a[i]);
	
	int ans=0;
	for(int i=1;i<=L+1;i++)
		ans=ans+a[i];
		
	cout< 
2.Tallest Cow
 开始时假设所有奶牛的高度为最高的高度，如果两个奶牛可以相互看见，则他们中间的奶牛高度减1.
 
#include
#include
//#include
using namespace std;
const int N=1e4+10;
int a[N],b[N];
void insert(int l,int r,int c)
{
	b[l]+=c;
	b[r+1]-=c;
}

int main()
{
	int n,I,h,p;
	cin>>n>>I>>h>>p;
	
	//初始化a数组 
	for(int i=1;i<=n;i++)
		a[i]=h;
	//初始化差分数组 
	for(int i=1;i<=n;i++)
		insert(i,i,a[i]);	
	
	
	//用来判断所给区间是否重复。
	set >st; //两个 > 之间有空格
	for(int i=0;i>a>>b;
		
		if(a>b) swap(a,b); 
		
		if(!st.count({a,b}))
		{
			st.insert({a,b});
			insert(a+1,b-1,-1);//(a b)之间的高度减一所以是[a+1 b-1]这个区间 
		}
	}
	
	//求出原数组
	for(int i=1;i<=n;i++)
		a[i]=a[i-1]+b[i];
	
	//输出高度
	for(int i=1;i<=n;i++)
		cout< 
3.铺设道路
 
构造差分序列：
 b1=a1
 b2=a2−a1
 b3=a3−a2
 ……
 bn=an−an−1
 bn+1=−an (bn+1只是为了便于证明,并没有用到)
 
因为最终结果原数组都为零，所以相应的差分数组也都是零，因为对原数组一个区间进行操作，对应的是差分数组两个元素进行操作(b[l]- -,b[r+1]++)。所以问题可以转化为: 每次对差分数组中其中一个元素减1，另一个元素加1，经过多少次后，可以使所有差分数组元素都为零。因为这里我们构造的差分数组之和等于零( ∑bi=0)，所以|∑b正|=|∑b负|(差分数组中正数之和等与负数之和),所以每次对正数减1的同时对负数加1,所以当正数减为0的同时负数也就加到了0,所以求出∑b正 即可.
 
#include
using namespace std;
const int N=1e5+10;
int a[N],b[N]; 
int main()
{
	int  n;
	cin>>n;
	
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	//初始化差分数组 
	for(int i=1;i<=n;i++)
		b[i]=a[i]-a[i-1];
	
	int ans=0;
	//把大于0的求和
	for(int i=1;i<=n;i++)
	{
		if(b[i]>0) ans+=b[i];	
	}
	
	cout< 
4.地毯
 二维差分模板题
 
#include
using namespace std;
const int N=1010;
int b[N][N];
void insert(int x1,int y1,int x2,int y2)
{
	b[x1][y1]++;
	b[x2+1][y1]--;
	b[x1][y2+1]--;
	b[x2+1][y2+1]++;
}
int main()
{
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		insert(x1,y1,x2,y2);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
		
	for(int i=1;i<=n;i++)
	{	
		for(int j=1;j<=n;j++)
			cout< 
5.假币问题
 因为是最坏的情况，所以如果是奇数张最先抽出来的那个一定不是假币,假币在剩下的那些当中.因此如果是奇数张，把个数减1,剩下的和偶数张处理方式一样;
 偶数张处理方式:用到了二分的思想,每次分为两份,取轻的那份继续分为两份,再取轻的那份继续此操作,直到每份为1;
 
#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	
	int cnt=0;
	while(n!=1)
	{
		if(n%2==1) n--;
		
		n=n/2;
		cnt++; 
	}
	cout< 
6.二分查找（一）
 二分模版题
 
#include
using namespace std;
const int N=1e5+10;
int a[N];
int n,m;
bool find(int x)
{
	int l=0,r=n-1;
	int mid;
	while(l>n>>m;
	for(int i=0;i>a[i];
	
	//需要先排序
	sort(a,a+n);
	 
	while(m--)
	{
		int x;
		cin>>x;
		if(find(x)) cout<<"YES"< 
7.查找最接近的元素
 先找出大于等于x的那一个数a[l]，所以最接近x的那个数一定是a[l]或者比a[l]小的那个数其中的一个
 
#include
using namespace std;
const int N=1e5+10;
int a[N];

int main()
{
	int n;
	cin>>n;
	
	for(int i=0;i>a[i];
	//因为题中已经说明是非降序列，所以不用再排序 
	
	int m;
	cin>>m;
	
	while(m--)
	{
		int x;
		cin>>x;
		
		int l=0,r=n-1,mid;
		//在a中查找>=x的数中最小的一个 
		while(l=x)  r=mid;
			else l=mid+1;
		}

		//处理边界，因为下面用到了l-1，
		//所以特判l==0的情况 
		if(l==0) cout<=x的数中最小的一个
			//所以与x最接近的只可能是a[l],a[l-1]之间的一个 
			int ans=(abs(x-a[l-1])>abs(x-a[l]))? a[l]:a[l-1];
			cout< 
第六题模板与第七题模板区别
 第六题模板是在序列a中查找<=x的数中最大的一个
 第七题模板是在序列a中查找>=x的数中最小的一个
 
8.银行贷款
 
 
#include
#include
using namespace std;
double x,y,n;
double sum(double a)
{
	double ans=0;
	for(int i=1;i<=n;i++)
	{
		double res=pow((a+1),i);
		ans +=y/res;
	}
	return ans;
}
int main()
{
	scanf("%lf%lf%lf",&x,&y,&n);
	//百分数表示是   0到1000%
	//转化为小数就是 0到10 
	double l=0,r=10;
	while(r-l>1e-4)
	{
		double mid=(l+r)/2;
		//由上面式子可知：当sum(mid)>=x，应该更新l为mid
		if(sum(mid)>=x) l=mid; 
		else r=mid;	
	}
	//结果用百分数表示 
	printf("%.1lfn",l*100);
	return 0;
}