自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:39:42，当前版本为作者最后更新于2022-07-20 13:38:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比较简单的贪心。

你以为你写的是暴力，其实和正解没什么差距（

subtask1~4

性质 A，B 都保证了答案的天数不会太多，所以有个 naive 的想法：直接贪心插入，不能插入了就睡。

然后就能过 70pts 了。

归纳证明。假设已经求出前 $i-1$ 个任务的答案，若再插入一个有更优方案，则在前 $i-1$ 个的时候就应该插入了，矛盾。

subtask5

发现，当整天睡觉的时候，70pts 的做法会 TLE。考虑优化这一过程。

每次插入一个的时候，如果当天不够了，就去计算要睡多少天才够。

可以做到线性。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
#define printYes puts("Yes")
#define printYES puts("YES")
#define printNo puts("No")
#define printNO puts("NO")
#define endl "\n"
#define lowbit(x) (x&(-x))

const ll inf=1000000000000000000; 
//const ll mod=998244353;
//const ll mod=1000000007;
#define int ll
const int N=500005;
ll n,m,p; 
int a[N];

inline int read()
{
    int F=1,ANS=0;
	char C=getchar();
    while (C<'0'||C>'9')
	{
		if (C=='-') F=-1;
		C=getchar();
	}
    while (C>='0'&&C<='9')
	{
		ANS=ANS*10+C-'0';
		C=getchar();
	}
    return F*ANS;
}
inline char readchar()
{
	char C=getchar();
    while (C<33||C>126) C=getchar();
    return C;
}
inline int raed(){return read();}

void work()
{
	//n=read();
	//for (int i=1;i<=n;i++) a[i]=read();
}

signed main()
{
	n=read(),m=read(),p=read();
	ll q = read();
	for (int j=1;j<=n;j++) a[j]=read();
	int ans1=0,ans2=0;
	int tot=1,sl=0;
	for (int j=1;;j++)
	{
		if (0<m*p*j-(m-a[tot]+sl)*q)
		{
			int i=(m*p*j-(m-a[tot]+sl)*q+(m*(q-p))-1)/(m*(q-p));
			j+=i,sl+=i*m;
		}
		int x=m;
		while (1)
		{
			if (tot==n+1) break;
			if (x<=a[tot]) break;
			if ((x-a[tot]+sl)*q<m*p*j) break;
			x-=a[tot],tot++;
		}
		sl+=x;
		if (tot==n+1)
		{
			ans1=j;
			break;
		}
	}
	cout << ans1;
	return 0;
}

再讲一种比较好写的做法。

可以发现，在可以的前提下，如果每次将任务往后挪，睡觉时间会发挥更大的价值，是不劣的。

所以，任何一个答案都可以转化成：前几天一直睡大觉，到最后加班加点赶工。

倒序插入任务，每次完成一天就更新要睡觉的天数就可以了。

/* name: c
 * author: 5ab
 * created at: 22-07-27 07:59
 */
#include <iostream>
using namespace std;

typedef long long ll;
const int max_n = 100000;

int a[max_n];

inline void chmax(ll& a, ll b) { if (a < b) a = b; }
inline ll cdiv(ll a, ll b) { return (a + b - 1) / b; }
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, x, p, q;
	ll sm = 0;
	
	cin >> n >> x >> p >> q;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sm += a[i];
	}
	
	ll ans = 0, cnt = 0, csm;
	for (int i = n - 1; i >= 0; )
	{
		chmax(ans, cnt + cdiv(sm * q, 1ll * x * (q - p)));
		// cerr << sm * q << " " << 1ll * x * (q - p) << endl;
		
		csm = 0;
		while (i >= 0 && a[i] + csm < x)
			csm += a[i--];
		sm -= csm, cnt++;
	}
	
	cout << ans << endl;
	
	return 0;
}