P8586 题解

_EternalRegrets_ · 2023-02-09 22:30:00 · 题解

P8586 题解

本题目是一道贪心题。

由题意可知，第 n 天仅可以处理第 n-1 天与第 n 天的陨石。

可以很简单地证明在第 i 天优先处理第 i-1 的陨石会更优一些。因为如果第 i 天优先处理第 i-1 天的陨石，可以让第 i+1 天需要处理的陨石质量减少到最小值，同时也确保了最多处理的陨石质量。

用一个桶去记录每天的陨石质量。

最后循环寻找答案。（特殊处理 0 时刻和最大天数 +1）

具体见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int maxn=0; //天数
int ans=0; //答案
int used; //本天已经打掉的质量
int a[500005]; //桶，记录每天有多少质量的陨石

signed main()
{
    int n; cin>>n;
    int k; cin>>k; //输入

    for (int i=1;i<=n;i++)
    {
        int d; cin>>d; //天数
        int m; cin>>m; //质量

        a[d]+=m; //桶
        maxn=max(maxn,d); //计算最大天数
    }

    for(int i=0;i<=maxn+1;i++) //maxn+1 天需处理 因为 maxn+1 天也可以抵挡 maxn 天的；0 时刻也需处理
    {
        if(i==0) //如果是0时刻
        {
            if(a[i]<k) //如果还没有达到上限
            {
                ans+=a[i];
                a[i]=0;  //归零
            }
            else //如果达到了上限
            {
                ans+=k;
                a[i]-=k;  //打掉可以打的数量
            }
        }
        else
        {
            if(a[i-1]<=k) //看前一天的
            {
                ans+=a[i-1];
                used=a[i-1];
                a[i-1]=0;   //归零
            }
            else
            {
                ans+=k;
                used=k;
                a[i-1]-=k;  //打掉可以打的质量
                continue;
            }

            if(a[i]<=k-used) //如果本天的还可以抵挡
            {
                ans+=a[i];
                a[i]=0;
            }
            else //还不可以就挑部分抵挡
            {
                ans+=k-used;
                a[i]=a[i]-k+used;
            }
        }
    }

    cout<<ans; //输出
    return 0;
}