贪心进阶

tkm2013 · 2024-10-10 19:19:34 · 算法·理论

今天我们继续来学习贪心。

例题

P9749 [CSP-J 2023] 公路

这道题中,我们的油箱是 \infty 的,所以不管装多少油都没事,所以我们可以把油价最便宜的记录下来,先在我们要从 i 到 i+1 了,就用最便宜的油价。由于我们的油箱 \infty 大所以我们可以提前买好油。还要开 long\ long

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d;
int v[100005];
int a[100005];
int cei(int x,int y){
    if(x%y==0){
        return x/y;
    }
    return x/y+1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int sum=0,minn=1e18,y=0;
    for(int i=1;i<n;i++){
        minn=min(minn,a[i]);//最便宜的油价
        int k=cei(v[i]-y,d);//只能买整数的油,向上取整
        sum+=k*minn;//花钱买油
        y=k*d+y-v[i];//计算跑过去后还能剩下多少油,在下次用
    }
    cout<<sum;
    return 0;
}

[USACO05MAR] Yogurt factory 机器工厂

这道题我们可以用和上题一样的做法,但是有一点是不一样的,这道题还多出来了一个保存费用,那么我们每多保存一星期,就要多花费 s 元来保护,所以我们可以在循环的最后让 minn 加上 s ,这个就是保护的花费,在和下一周直接做的作对比。

Code

#include<bits/stdc++.h>
using namespace std;
long long c[10005],y;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,s;
    cin>>n>>s;
    long long sum=0;
    long long minn=1e9;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>y;
        minn=min(minn,c[i]);//这星期做是否是最便宜
        sum+=minn*y;//做y台的成本
        minn+=s;//保存到下一周所需要的钱
    }
    cout<<sum;
    return 0;
}

P1016 [NOIP1999 提高组] 旅行家的预算

这道题似乎和第一题一样,但是油箱却有了大小的限制,所以在思路上也会有很大的区别普及组第三题和普及组第二题只需一个油箱。由于有了油箱就不能简单的取最小值了,但是这道题给了我们一条活路,那就是可以加小数升油。

首先我们来考虑输出No Solution的情况,如果两个相邻的站点(包括起点和终点),之间的距离就算把油箱加满了也开不过去,就输出No Solution。

for(int i=2;i<=n;i++){
    if(a[i].d-a[i-1].d>k*c){
        cout<<"No Solution";
        return 0;
    }
}

①