10.11 贪心++++

xuanxiao2024 · 2024-10-11 12:06:22 · 个人记录

P2616 [USACO10JAN] Buying Feed, II S

时间复杂度

1 \le N \le 100

最大 O(n ^ 4)

细节

没有消耗，只有购买

思路

看起来很唬人，实际上很简单。由于没有消耗，所以直接贪费用，在费用低的店多买一些。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    ll x,y;
    bool operator < (const node& b) const{
        return x < b.x;
    }
};
ll n,m,e,ans;
node a[105];

int main(){
    cin >> m >> e >> n;
    for(int i = 1;i <= n;i++){
        ll x,f,c;
        cin >> x >> f >> c;
        a[i].x = c + (e - x);
        a[i].y = f;
    }
    sort(a + 1,a + 1 + n);
    for(int i = 1;i <= n;i++){
        if(m > a[i].y){
            m -= a[i].y;
            ans += a[i].x * a[i].y;
        }else{
            ans += m * a[i].x;
            break;
        }
    }
    cout << ans;
    return 0;
}

P2836 加油问题

时间复杂度

n \le 51

最高时间复杂度: O(n^{5})

细节

若油箱里的油大于一半，无法主动停下(被动指的是无法到达下一站)
每一个停下来的，必须加满，还得买糖果
加油站出售的汽油每加仑的价格单位是分，需要转为元。
最开始油是加满了的。
思路

本题无法直接通过别的算法找到到底在哪几个站加油最便宜。看见数据范围较小，可以直接 DFS ，暴力求解。 DFS 会传这样几个参数: 当前站 ， 当前还有多少油 和 目前花了多少 对于每一个 DFS 状态，我们做以下讨论：
- 若当前已经到达终点，则直接将当前花费与答案比较，取最小值
- 若当前没有到达终点并且当前油量大于等于一半:
- 若当前油足以到达下一个加油站，则不加油
- 否则必须加油
- 若当前没有到达终点并且当前油量小于一半:
- 若不足到达下一个点，则加油
- 若足以到达下一个点:
  - 加油
  - 不加油

由于 2^{51} 次方比较大，所以我们需要加最优性剪枝:

若当前花费已经比答案大了，则通过自己得到的 DFS 状态的花费一定不小于答案，所以直接返回
Code
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
double e,c,l,s,ans = 1e18,v[55],w[55];
```

void dfs(ll step,double oil,double cnt){ if(cnt > ans) return ; if(step == n + 1){ if(ans > cnt){ ans = cnt; } return ; } if(oil >= c / 2){ if((w[step + 1] - w[step]) / l > oil){ dfs(step + 1,c - (w[step + 1] - w[step]) / l,cnt + (c - oil) v[step] + 2); }else{ dfs(step + 1,oil - (w[step + 1] - w[step]) / l,cnt); } }else{ dfs(step + 1,c - (w[step + 1] - w[step]) / l,cnt + (c - oil) v[step] + 2); if((w[step + 1] - w[step]) / l <= oil){ dfs(step + 1,oil - (w[step + 1] - w[step]) / l,cnt); } } return ; }

int main(){ cin >> e >> c >> l >> s >> n; for(int i = 1;i <= n;i++){ cin >> w[i] >> v[i]; v[i] /= 100; } w[n + 1] = e; dfs(1,c - w[1] / l,s); printf("%.2lf",ans); return 0; }

## [P1887 乘积最大 3](https://www.luogu.com.cn/problem/P1887)
#### 时间复杂度
`1 <= n <= 1e9,1 <= m <= 1e6`
时间复杂度大约为 `O(m) 或 O(m log n)`
#### 细节
是和为 `n` 的 `m` 个正整数
#### 思路
` 和一定，差小积大 `
在此处，所有数的差的绝对值都可以小于等于 1
此时是 `m - n % m` 个 `n / m` 与 `n % m` 个 `n / m + 1`
### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;

int main(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        if(i <= m - n % m) cout << n / m << " ";
        else cout << n / m + 1 << " ";
    }
    return 0;
}

P9787 [ROIR 2020 Day2] 最大乘积

时间复杂度

2 <= n <= 2e5 考虑 O(n) 或 O(n log n) 的写法

细节

如果直接乘，会爆 long long

思路

还是 和一定，差小积大 直接用前缀和维护静态区间和，枚举断点，直接找差绝对值最小。

Code

P8669 [蓝桥杯 2018 省 B] 乘积最大

时间复杂度

1 <= k <= n <= 100000 O(n) 或 O(n log n)

细节

负负得正

思路

若 k 为奇数，则选最大的，k - 1:

若最大的为负数，说明所有的都是负数，f = -1(f 初值为 1) 然后从两端分别取两个数，看哪边乘积大 (还要乘上 f ) ，最后输出即可。
Code
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 9;
ll n,m,ans = 1,f = 1;
ll a[100005];
```

int main(){ cin >> n >> m; for(int i = 1;i <= n;i++){ cin >> a[i]; } sort(a + 1,a + 1 + n); if(m & 1 == 1){ ans = a[n]; n--; m--; if(ans < 0){ f = -1; } } ll l = 1,r = n; while(l < r && m > 0){ if(f a[l] a[l + 1] > f a[r] a[r - 1]){ ans = (ans a[l]) % mod; ans = (ans a[l + 1]) % mod; l += 2; m -= 2; }else{ ans = (ans a[r]) % mod; ans = (ans a[r - 1]) % mod; r -= 2; m -= 2; } } cout << ans; return 0; }