YbtOJ 「基础算法」第3章 二分算法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N];
int maxn,s;
int check(int x)
{
	int cnt=1,sum=0;
	for(int i=1;i<=n;i++)
	{
		if(sum+a[i]>x) cnt++,sum=a[i];
		else sum+=a[i];
	}
	//cout<<x<<" "<<cnt<<endl;
	return cnt;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),maxn=max(maxn,a[i]),s+=a[i];
	int l=maxn,r=s;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)<=m) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}
/*
6 3
4 2 4 5 1 1
*/

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N=2e5+5;
int T,n,s[N],e[N],d[N];
int check(int x)
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]>x) continue;
		sum+=(min(e[i],x)-s[i])/d[i]+1;
	}
	return sum;
}
signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&s[i],&e[i],&d[i]);
		long long l=1,r=(long long)(1ll<<31ll)-1ll;
		if((check(r)&1)==0) {cout<<"There's no weakness."<<endl;continue;}
		//cout<<l<<" "<<r<<endl;
		while(l<r)
		{
			int mid=(l+r)>>1;
			//cout<<mid<<" "<<check(mid)<<endl;
			if((check(mid)&1)==0) l=mid+1;
			else r=mid;
		}
		cout<<l<<" "<<check(l)-check(l-1)<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=1e5+5;
const db eps=1e-5;
int n,l,a[N],maxn;
db b[N];
bool check(db x)
{
	db minn=1e9;
	for(int i=1;i<=n;i++) b[i]=1.0*a[i]-x;
	//for(int i=1;i<=n;i++) cout<<b[i]<<" ";
	//cout<<endl;
	for(int i=1;i<=n;i++) b[i]=b[i-1]+b[i];
	for(int i=l;i<=n;i++)
	{
		minn=min(minn,b[i-l]);
		//cout<<i<<" "<<b[i]<<" "<<minn<<endl;
		if(b[i]-minn>=-eps) {return 1;}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),maxn=max(maxn,a[i]);
	db l=-1e9,r=maxn;
	while(r-l>eps)
	{
		db mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.0lf\n",l*1000.0);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,t,h[N],g[N],c[N];
int minn=2e9;
int check(int x)
{
	for(int i=1;i<=n;i++) c[i]=h[i]+g[i]*(x-1);
	sort(c+1,c+n+1);
	int sum=0;
	for(int i=1;i<=x;i++) sum+=c[i];
	return sum;
}
int main()
{
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]),minn=min(minn,h[i]);
	for(int i=1;i<=n;i++) scanf("%d",&g[i]);
	if(minn>t) {cout<<"0"<<endl;return 0;}
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(check(mid)<=t) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,s,k[N],b[N],c[N];
bool check(int x)
{
	for(int i=1;i<=n;i++) c[i]=k[i]*x+b[i];
	nth_element(c+1,c+m,c+n+1,greater<int>());
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		if(c[i]<0)continue;
		sum+=c[i];
		if(sum>=s) return 1;		
	}
	return 0;
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&k[i],&b[i]);
	int l=1,r=1e9;
	if(check(0)) {cout<<"0"<<endl;return 0;}
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int s,n,m,a[500005];
int check(int x)
{
	int now=0,ans=0;
	for(int i=1;i<=n+1;i++)
	{
		if(a[i]-a[now]<x) ans++;
		else now=i;
	}
	return ans;
}
int main()
{
	scanf("%d%d%d",&s,&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	a[n+1]=s;
	int l=1,r=s,mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(check(mid)>m) r=mid-1;
		else l=mid;
	}
	cout<<r<<endl;
	return 0;
}