链接：https://www.nowcoder.com/questionTerminal/7f080ec10f4e46c2bd13ea8b565273d0
来源：牛客网
来源：牛客网
因为公司有免费健身福利，快手程序员老铁们都很爱健身，而且他们健身时像工作一样充满效率。
他们把健身过程神奇的简化了出来：健身有N种锻炼方式可选，器材可看成在一条直线上。
每种锻炼方式距门口Xi米，因为有的器材上可以支持多种锻炼方式，因此有可能出现两种锻炼方式的距离是一样的，即Xa = Xb。
老铁们一进健身房门口就开启健身形态，每走1米，就能获得1点锻炼效果值，而每种锻炼方式也有Ei的效果值，锻炼的过程就是从门口走到某种锻炼方式锻炼，然后到下一个方式锻炼，最后返回门口的过程。需要注意的是，锻炼过程中老铁们不会为了获得效果而刻意走回头路。
老铁们很想知道如果想选择某几种锻炼方式，怎样获得最大锻炼效果。
输入描述:
第一行N，表示锻炼方式的个数 第二行N个整数，表示每种锻炼方式距门口的距离 第三行N个整数，表示每种锻炼方式的效果值
输出描述:
N个整数，第k行表示选择k种锻炼方式时获得的最大锻炼效果
示例1
输入
5 1 2 3 4 5 1 1 1 1 1
输出
11 12 13 14 15
说明
对于样例第一行，老铁选择去第5种锻炼方式，考虑来回路程，一共获得5+1+5点锻炼效果值
备注:
对于所有数据，N <= 100,000，输出结果在32位整数范围内
解析：
首先，这道题的测试数据的确不合理。
具体可以参考由Bugboy 提供的测试用例：
5 1 4 5 6 7 10 2 9 1 1
输出为：
19 29 34 36 37
下面看菜鸡如何一步一步地优化😂。
1.dfs暴力，首先想到的办法就是暴力，在每一个器材上，只有两种选择——选择该器材或者不选择该器材，代码很简单，具体细节可以参见代码。当输入长度为n时，时间复杂度为O(2n)，最终通过20%。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100005;
int book[maxn];
struct node {
int dis;
int value;
};
node vec[maxn];
int n;
void dfs(int start,int value,int num, int max_dis){
if (start>n){
return;
}
if(book[num]<max_dis*2+value){
book[num]=max_dis*2+value;
}
dfs(start+1,value+vec[start].value,num+1,max(max_dis,vec[start].dis));
dfs(start+1,value,num,max_dis);
return;
}
int main(){
cin>>n;
for (int i = 0; i <n ; ++i) {
cin>>vec[i].dis;
}
for (int i = 0; i <n ; ++i) {
cin>>vec[i].value;
}
dfs(0,0,0,0);
for (int i = 1; i <=n ; ++i) {
cout<<book[i]<<endl;
}
return 0;
}
2.暴力不行，我就想到了动态规划。先按照距离升序对器材进行排序，保证后面的器材比前面的器材距离大。然后就是动态规划，matrix[i][j]表示前i个器材中选择j个，并且i必选时的最大能量。matrix[i][j]应该等于前i-1个器材中选择j-1个器材的最大效果值，然后再加上第i个器材效果和2倍的第i个器材的距离。那么递推公式为： matrix[i][j]=max0<=k<=i-1{matrix[k][j-1]+valuei+disi*2-valuek}
其中valuei，disi表示第i个效果值和距离。
其中valuei，disi表示第i个效果值和距离。
具体代码如下，当输入长度为n时，时间复杂度为O(n3)，最终通过40%。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100005;
int book[maxn];
struct node {
int dis;
int value;
int total;
};
node vec[maxn];
int n;
int cmp(node a ,node b){
return a.dis<b.dis;
}
int matrix[maxn][maxn];
int main(){
cin>>n;
for (int i = 0; i <n ; ++i) {
cin>>vec[i].dis;
}
for (int i = 0; i <n ; ++i) {
cin>>vec[i].value;
vec[i].total=vec[i].dis*2+vec[i].value;
}
sort(vec,vec+n,cmp);
matrix[1][1]=vec[0].dis*2+vec[0].value;
for (int i = 1; i <=n ; ++i) {
for (int j = 1; j <=i ; ++j) {
for (int k = 1; k <=i-1 ; ++k) {
if(matrix[i][j]<matrix[k][j-1]+vec[i-1].value+vec[i-1].dis*2-(matrix[k][j-1]>0?vec[k-1].dis*2:0)){
matrix[i][j]=matrix[k][j-1]+vec[i-1].value+vec[i-1].dis*2-(matrix[k][j-1]>0?vec[k-1].dis*2:0);
}
}
}
}
for (int i = 1; i <=n ; ++i) {
int max_v=0;
for (int j = i; j <=n ; ++j) {
if (max_v<matrix[j][i]){
max_v=matrix[j][i];
}
}
cout<<max_v<<endl;
}
return 0;
}
3.贪心，这个很明显具有最优子结构的性质，也具有贪心选择性。每一次选择都选择效果值增加最多的那个器材。当输入长度为n时，需要做n次选择，每一次选择需要花费O(n)的时间，所以总的时间复杂度为O(n2)，最终通过60%。 #include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=100005;
int book[maxn];
struct node {
int dis;
int value;
int total;
};
node vec[maxn];
int n;
int main(){
cin>>n;
for (int i = 0; i <n ; ++i) {
cin>>vec[i].dis;
}
for (int i = 0; i <n ; ++i) {
cin>>vec[i].value;
vec[i].total=vec[i].dis*2+vec[i].value;
book[i]=0;
}
int j=0,index=0;
while (j<n){
for (int i = 0; i <n ; ++i) {
if(vec[index].total<vec[i].total)index=i;
}
book[j+1]=book[j]+vec[index].total;
for (int i = 0; i < n; ++i) {
if(i==index) continue;
if(vec[index].dis>=vec[i].dis){
vec[i].dis=0;
vec[i].total=vec[i].value;
} else{
vec[i].dis=vec[i].dis-vec[index].dis;
vec[i].total=vec[i].dis*2+vec[i].value;
}
}
vec[index].value=0;
vec[index].total=0;
vec[index].dis=0;
j++;
}
for (int i = 1; i <=n ; ++i) {
cout<<book[i]<<endl;
}
return 0;
} 4.贪心的优化。上面的贪心算法中，每一次选择需要花费太长的时间，可以进一步地优化。我们需要认识到每一次选择的器材有一个特点，就是每一次选择的器材是剩下的器材中，效果值value最大的或者是距离dis最大的。所以可以使用两个优先队列来完成每一次选择器材。当输入长度为n时，时间复杂度为O(nlogn)，最终通过100%。
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=100005;
int book[maxn];
int record[maxn];
struct node {
int index;
int dis;
int value;
int total;
};
struct cmp1{
bool operator()(node a,node b){
return a.value<b.value;
}
};
struct cmp2{
bool operator()(node a ,node b){
return a.total<b.total;
}
};
node vec[maxn];
int n;
priority_queue <node,vector<node>,cmp1> q_max_value;
priority_queue <node,vector<node>,cmp2> q_max_total;
int main(){
cin>>n;
for (int i = 0; i <n ; ++i) {
cin>>vec[i].dis;
}
for (int i = 0; i <n ; ++i) {
cin>>vec[i].value;
vec[i].index=i;
vec[i].total=vec[i].dis*2+vec[i].value;
q_max_total.push(vec[i]);q_max_value.push(vec[i]);
}
int j=0,last_dis=0;
node t_max_total,t_max_v;
while (j<n){
if (!q_max_total.empty()){
t_max_total=q_max_total.top();
q_max_total.pop();
while (record[t_max_total.index]!=0&&(!q_max_total.empty())){
t_max_total=q_max_total.top();
q_max_total.pop();
}
}
if (!q_max_value.empty()){
t_max_v=q_max_value.top();
q_max_value.pop();
while (record[t_max_v.index]!=0&&(!q_max_value.empty())){
t_max_v=q_max_value.top();
q_max_value.pop();
}
}
if(t_max_total.total-(t_max_total.dis>last_dis?2*last_dis:2*t_max_total.dis)>t_max_v.total-(t_max_v.dis>last_dis?2*last_dis:2*t_max_v.dis)){
book[j+1]=book[j]+t_max_total.total-(t_max_total.dis>last_dis?2*last_dis:2*t_max_total.dis);
last_dis=max(t_max_total.dis,last_dis);
record[t_max_total.index]=1;
q_max_value.push(t_max_v);
} else {
book[j+1]=book[j]+t_max_v.total-(t_max_v.dis>last_dis?2*last_dis:2*t_max_v.dis);
last_dis=max(t_max_v.dis,last_dis);
record[t_max_v.index]=1;
q_max_total.push(t_max_total);
}
j++;
}
for (int i = 1; i <=n ; ++i) cout<<book[i]<<endl;
return 0;
} 
京公网安备 11010502036488号