贪贪

· · 个人记录

P2616 [USACO10JAN] Buying Feed, II S

这道题目和背包有点像。方法吗~，首先要求的是最小的花费那么我们就可以用用背包的思路。

那么背包的思路是什么呢，不就是买当前最有吗，那么我们就可以看看，剩下的钱能买完当前最便宜的商品吗。如果可以就买完否则买一部分。

code

#include<bits/stdc++.h>
using namespace std;
int k,e,n;
struct pi{
    int num,cnt;
}s[1005];
bool cmp(pi x,pi y){
    return x.cnt < y.cnt;
} 
int main(){
    cin >> k >> e >> n;
    for(int i = 1 ; i <= n ; i ++){
        int a,b,c;
        cin >> a >> b >> c;
        s[i].num = b;
        s[i].cnt = e - a + c;
    }
    sort(s + 1 , s + 1 + n , cmp);
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(k > s[i].num){
            ans += s[i].cnt * s[i].num;
            k -= s[i].num;
        }else{
            ans += min(s[i].num , k) * s[i].cnt;
            break;
        }
    }
    cout << ans;
    return 0;
}

P1180 驾车旅游

这道题目我们可以用搜索的方法求解。那么我们就要进行分类讨论。

当剩下的油数能到达下一个加油站，我们就分两种情况讨论：

① 当剩下的油量要大于总容量的一半时，我们是不能停下来加油的，这是题目的要求。

② 否则的话，我们就有两种情况了，在这个加油站你即可停下来加油，也可以继续往后走，那么你就可以直接搜索两种情况。

这里还有一个被动条件，也就是被动触发的。就是当剩下的油数不能到达下一个加油站，就必需要加满油。否则你就到达不了终点了。

然后其实我们还可以优化一下时间，比如你现在求出的答案就大于了我们以前求出的答案，那么就不用找了不可能在更小了。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dis;
double maxn,mile,st;
int n;
int half;
double ans = 1e10;
struct node{
    int dis;
    double fare;
}a[55];
void dfs (int cur,double oil,double cost){
    if(cost > ans)return ;
    if(cur == n + 1){
        ans = min(ans , cost);
        return ;
    }
    if(oil * mile >= a[cur + 1].dis - a[cur].dis){
        if(oil >= half){
            dfs(cur + 1, oil - (a[cur + 1].dis - a[cur].dis) / mile, cost);
        }
        else{
            dfs(cur + 1 , oil - (a[cur + 1].dis - a[cur].dis) / mile, cost);
            dfs(cur + 1 , maxn - (a[cur + 1].dis - a[cur].dis) / mile , cost + 20 + (maxn - oil) * a[cur].fare);
        }
    }
    else{
        dfs(cur + 1 , maxn - (a[cur + 1].dis - a[cur].dis) / mile , cost + 20 + (maxn - oil) * a[cur].fare);
    }
    return ;
}
signed main(){
    cin >> dis >> maxn >> mile >> st >>n;
    half = maxn / 2;
    for(int i = 1; i <= n; i ++){
        cin >> a[i].dis >> a[i].fare;   
    }
    n ++;
    a[n].dis = dis;
    a[n].fare = 0.0;
    dfs(1, maxn - a[1].dis / mile, st);
    printf("%.1lf", ans);
    return 0;
}

P9787 [ROIR 2020 Day2] 最大乘积

首先我们要知道一个特性才能做这道题目。那就是当两个数的和一样时，差越小乘积越大。

然后题目只让我们找到一个中间点就可以了，那么我们就可以直接从 1 枚举到 n 然后去找差最小的答案。

还有再求两边答案的时候不要傻傻的在开一重循环去找左右两边的和了。我们可以用前缀和求出答案的。（别忘了开 long long）

code

#include<bits/stdc++.h>
using namespace std;
long long sum[200005],a[200005],maxn = 1e18,x;
int n;
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for(int i = 1 ; i < n ; i ++){
        if(maxn > abs((sum[n] - sum[i]) - sum[i])){
            maxn = abs((sum[n] - sum[i]) - sum[i]);
            x = i;
        }
    }
    cout << x;
    return 0;
}