当前位置：首页 > news >正文

A - dry

news 来源：原创 2024/5/3 20:50:58

贪心+堆可过

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
inline void read(LL& x)
{
	char c=getchar();bool flag=0;x=0;
	while(c<'0'||c>'9'){if(c=='-')flag=true;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	flag?x=-x:1;
}

LL n,A,B,now = 0;
priority_queue<LL> q;
int main(void)
{
#define ACK
#ifdef ACK
	freopen("dry.in","r",stdin);
	freopen("dry.out","w",stdout);
#endif
	read(n),read(A),read(B);
	LL t;
	for(register int i=1;i<=n;i++)
	{
		read(t);
		q.push(t);
	}
	LL Max,cnt = 1;
	while(!q.empty())
	{
		Max = q.top();q.pop();
		if(Max<=A*cnt)break;
		cnt++;
		Max-=B;
		q.push(Max);
	}
	printf("%d",cnt);
	return 0;
}

或者二分答案。【贪心好写但是二分答案要快。。当然不是裸二分，二分答案你可以很显然地推出一个上下界。。当然直接飙极限也可以，但是注意防int溢出】

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
inline void read(long long& x)
{
	char c=getchar();bool flag=0;x=0;
	while(c<'0'||c>'9'){if(c=='-')flag=true;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	flag?x=-x:1;
}
#define maxn 500010
long long n,A,B;
long long a[maxn],Max=0,cnt,cut;
inline bool check(long long t)
{
	long long res = t;
	for(int i=1;i<=n;i++)
	{
		if(res<0)return false;
		if(a[i]>t*A){
			res-=(a[i]-t*A)/B;
			if((a[i]-t*A)%B!=0)res--;
		}
	}
	return res>=0?true:false;
}
int main(void)
{
#define ACK
#ifdef ACK
	freopen("dry.in","r",stdin);
	freopen("dry.out","w",stdout);
#endif
	read(n),read(A),read(B);
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		Max = max(Max,a[i]);
	}
	long long low = Max/(A+B),high = Max/A+(Max%A==0?0:1);
//	int low = 1,high = maxn;
	long long ans=low,mid;
	while(low<=high)
	{
		mid = (low+high+1)/2;
		if(check(mid)){
			ans = mid;
			high = mid-1;
		}else
		{
			low = mid+1;
		}
	}
	printf("%I64d",ans);
	return 0;
}