洛谷P2672 推销员 题解 贪心
2024-08-30 20:06:53
题目链接:https://www.luogu.org/problem/P2672
这道题目是贪心,贪心的思想是:
选择 \(m\) 户人家的最大疲劳值应该是以下两种方案中的较大值:
- 方案一:选择 \(a[i]\) 最大的 \(m\) 户人家;
- 方案二:选择 \(a[i]\) 最大的 \(m-1\) 户人家,以及剩下的 \(n-(m-1)\) 户人家中 \(2 \times s[i] + a[i]\) 最大的那户人家
所以,我们可以给 \(n\) 户人家按照 \(a[i]\) 从大到小金星排序。
然后在开三个数组(这3个数组用到了DP来进行求解):
suma[i]
:表示 \(\sum_{j=1}^{i}a[j] + 2 \times \max_{j=1}^{i}(s[j])\) ,推导公式:suma[i] = suma[i-1] + a[i]
maxs[i]
:表示 \(\max_{j=1}^{i} s[j]\) ,推导公式:maxs[i] = maxs[i-1] + s[i]
maxsa[i]
:表示 \(\max_{j=i}^{n} (2 \times s[j] + a[j])\) ,推导公式:maxsa[i] = max(maxsa[i+1], 2 \times s[i] + a[i])
然后我们要在 \(n\) 户人家里面选择 \(m\) 户人家访问的最大疲劳值就是 sum[m] + 2 * maxs[m]
和 suma[m-1] + 2 * maxs[i]
的较大值。
实现代码如下:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int n, s[maxn], a[maxn], idx[maxn], suma[maxn], maxs[maxn], maxsa[maxn];
bool cmp(int i, int j) {
return a[i] > a[j];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> s[i];
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) idx[i] = i;
sort(idx+1, idx+1+n, cmp);
for (int i = 1; i <= n; i ++)
suma[i] = suma[i-1] + a[idx[i]], maxs[i] = max(maxs[i-1], s[idx[i]]);
for (int i = n; i >= 1; i --)
maxsa[i] = max(maxsa[i+1], s[idx[i]] * 2 + a[idx[i]]);
for (int i = 1; i <= n; i ++)
cout << max(suma[i]+2*maxs[i], suma[i-1]+maxsa[i]) << endl;
return 0;
}
最新文章
- No module named django.core
- linq group by max 多表链接实例
- Android开发涉及有点概念&;相关知识点(待写)
- /WEB-INF/userManage.jsp(31,82) Unterminated ${ tag
- MySql计数器,如网站点击数,如何实现高性能高并发的计数器功能
- HTTP返回码总结
- java多线程之Future和FutureTask
- CentOS5下配置JDK1.6+TOMCAT6
- 174. Dungeon Game
- Android Fragment学习(一)
- Objective C assign&;copy &; retain区别
- php Mysql 和Mysqli数据库函数整合
- ASP.NET弹出提示点击确定之后再跳转页面的方法
- 201521123039 《java程序设计》第十周学习总结
- 创建以mybatis为基础的web项目(1)
- 还是要习惯在linux环境下作Java开发
- Java File mkdir() mkdirs()
- (零)SQL server安装配置
- Eclipse + Pydev问题 : pydev unresolved import
- Sort aborted Error in MySQL Error Log