贪心

· · 个人记录

F1828 【基础】小猫吃鱼：fish.cpp

首先我们看看数据范围 n <= 100 时间不大，那么我们就可以想一想用到的算法。是 floyd,贪心，暴力搜索等。

然后我们来看看题目。题目给出的是要我们买鱼的最小花费，那么我们可以考虑一下贪心。假设是贪心我们要怎么贪呢？

首先要求我们求的是最小花费，那么我们买鱼的话肯定是尽量买钱少的啊。所以我们每次买鱼就看看要不要再这里买。

比如你现在在 i 点那么你就可以考虑要不要帮以后的自己买。那么我们因该怎么判断呢？首先假设在这个位置买的话我们能不能求出到 j 点为了这条鱼花了多少钱呢。

当然是可以的，因为我们知道从这里保养到下一站的保养费是多少。那么从 i 帮 j 点买鱼要花多少钱。不就是到 i 的买鱼的加钱加上所有保养费吗。

那么只要这些钱和到 j 点再买鱼要便宜我们就在 i 点顺便帮 j 点的鱼给买了，这样我们没到一个点所花费的钱数就是最小的，总钱数自然就更小了。

code

#include<bits/stdc++.h>
using namespace std;
int n,sum,cnt;
struct pi{
    int x,y;
}s[1005]; 
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> s[i].x >> s[i].y;
    }
    for(int i = 1 ; i <= n ; i ++){
        if(cnt > 0){
            cnt --;
            continue;
        }
        sum += s[i].x;
        int ans = s[i].y;
        for(int j = i + 1 ; j <= n ; j ++){
            if(s[j].x > ans + s[i].x){
                cnt ++;
                sum += ans + s[i].x;
                ans += s[j].y;
            }else{
                break;
            }
        }
    }
    cout << sum;
    return 0;
}

P9749 [CSP-J 2023] 公路

首先油箱一开始是空的，并且油箱的容量是无限的。题目要求的又是从 1 号点到 n 号点的最小油费是多少。那么我们可以考虑一下贪心。

首先想要油费尽可能的少，那么我们走每一段的所花费的油费就要尽可能的小才可以。那么怎样才能让这一段的油费最小呢。

那么我们是不是肯定优先考虑加油站的油费尽可能的小啊。然后油箱又支持我们买很多的油。

那么，我们就可以从现在所在的点，到达后面中比第一个比自己小的点。这个时候我就要问了，为什么不是到最小油价的点呢。

因为，你找到第一个比自己小的点和直接到达最小的点的为置是不一样的。最小的那个点是不可能比第一个比自己小的点要更加靠近我的。

那么我们假设现在在 i 第一个比自己小的点在 j ，最小的点在 k 保证中间没有比自己更小的点了。

然后你直接到 k 和 先到 j 再到 k 。就像 j 到 k 这一段距离你所耗费的油费是较大的，而到 j 后用 j 位置的油费要比原来位置要小，那么就会优化 j 到 k 这一段。

然后如果后面没有油价比自己更小的了那么你就不要在傻傻的跑去其它油站直接去终点因为油箱支持，并且加钱合适。

注意了你只能买整数升的油那么你就可能路程会多走一点。那么，多走的路程可以让你去到一个点的时候要买的油更少所以要记录一下。

还有在求卖多少升的时候要向上取整，否则可能会导致你买的油不够你到你要去的地方。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,m,num;
int a[100005],b[100005];
signed main(){
    cin >> n >> d;
    for(int i = 1 ; i < n ; i ++){
        cin >> a[i];
    }
    for(int j = 1 ; j <= n ; j ++){
        cin >> b[j];
    }
    for(int i = 1 ; i < n ; i ++){
        if(m >= a[i]){
            m -= a[i];
            continue;
        }
        int x = i,minn = b[i],sum = 0;
        for(int j = i + 1 ; j <= n ; j ++){
            sum += a[j - 1];
            x = j;
            if(b[j] < minn){
                minn = b[j];
                break;
            }
        }
        sum -= m    ;
        int k = ceil(1.0 * sum / d);
        num += k * b[i];
        m = d * k - sum;

        i = x - 1;
    }
    cout << num;
    return 0;
}

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

这道题目的整体思路是不变的，但是有好多个地方需要注意一下。

首先就是油箱是有限制的了，那么你就不能直接到达后面的任意地方，因为油箱可能会罢工不干了。

还有它的格式和上面哪一题有一些区别，上面的哪一题给定的是两点之间的距离，但是这道题却是给定的是与起点之间的距离。那么你就要重新求一下距离了。

然后我们就来解决一下到达不了的问题。那么怎样才能达到不了呢。不就是每次只往后走一个这样每次走的是最短距离。如果这都不能让我到达。我就不可能成功了。

然后我就来说说困了我那么久的几个坑点在哪里。

① 你想后找最小值的时候切忌千万不能超出了油箱在满的情况下能带你走的距离是多少。这其实不算啥坑点

② 困了我三百年的地方假设你一直往后找，直到达到了油箱能带我走的最远距离都找不到比当前小的情况下。

你就要直接到达，能到达的地方中的最小油价，但是，油箱不能只加到这个位置，而要加满这样才能为后面的油价省钱。因为这时候你用的是原来最小的油价啊。

所以为了这种情况我们还有记录一下，要走的距离直接拉满，然后这个位置到下一个位置的距离减少。你也可以用变量存储。

③ 这里我们如果遇到了更好的加油站，就只买能到这个加油站的钱，一分也不要多花。这样哪怕是接下来的 0.00001 的油也是按最小的来的。

④ 最简单的问题由于起点的油价都是题目直接给的不会放在数组里面。那么我们就为了使我们好检查手动放一下。

不要忘记把最后的位置也手动放置一下。那么我们再放置完后 n 要加1的，放最后一段之前也要加1。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
double d,num,c,kk;
int n;
double a[10005],b[10005],dd[10005];
signed main(){
    cin >> kk >> c >> d >> a[1] >> n;
    n ++;
    c *= d;
    for(int i = 2 ; i <= n ; i ++){
        cin >> dd[i] >> a[i];
        b[i] = dd[i] - dd[i - 1];
    }
    n ++;
    b[n] = kk - dd[n - 1];
    dd[n] = kk;
    for(int i = 1 ; i < n ; i ++){
        if(b[i + 1] - b[i] > c){
            cout << "No Solution" << endl;
            return 0;
        }
        double minn = a[i],sum = 0;
        int x = i;
        for(int j = i + 1 ; j <= n ; j ++){
            if(sum + b[j] > c)continue;
            sum += b[j];
            x = j;
            if(a[j] <= minn){
                minn = a[j];
                break;
            }
        }
        if(a[x] > a[i]){
            sum = dd[i] + c;
            b[x + 1] = dd[x + 1] - sum;
            sum = c;
        }
        num += sum / d * a[i];
        i = x - 1;
    }
    printf("%.2lf" , num);
    return 0;
}