普及模拟赛 R1 C 题解

5ab_juruo · 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;
}