复赛4:推销员

洛谷P2672

方法一:暴力(40分)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**************************************************************** 
 * Description: 2015年普及组复赛第四题 推销员
 * Author: Alex Li
 * Date: 2023-10-31 11:40:18
 * LastEditTime: 2023-10-31 17:42:52
****************************************************************/
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100005],b[1000005],c[100005];

int main(){
    int sum=0;
    cin>>n;

    for (int i = 1; i <=n; i++)cin>>a[i];
    for (int i = 1; i <=n; i++)cin>>b[i];

    for (int i = 1; i <=n; i++){
          int sum=0;
          int maxn=0;
          for (int j = 1; j <=n; j++){
            if(j<i)continue;
             maxn=0;
             for (int k = 1; k <=j-1; k++)c[k]=b[k];
                
            sort(c,c+j);
                              
            for (int k = j-1; k >=j-i+1; k--)maxn=maxn+c[k];
                
            maxn+=2*a[j]+b[j];
           sum=max(sum,maxn);                  
          }
          cout<<sum<<endl;
    }
}

方法二:利用排序数组进行贪心,满分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**************************************************************** 
 * Description: 2015年普及组复赛第4题,推销员 解法二
 * Author: Alex Li
 * Date: 2023-11-01 10:41:55
 * LastEditTime: 2023-11-04 13:07:13
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

struct node{
    int d;  //距离
    int v;  //疲劳值
}a[100005];
int pre[100005];//按疲劳值排序后,取i之前的疲劳值之和,
int last[100005]; //之后
int preMax[100005]; //前i项中,距离最大值 
int n;

bool cmp(node x,node y){
    return x.v>y.v;
}

int main(){
    cin>>n;
    for (int i = 1; i <=n; i++)cin>>a[i].d;
    for (int i = 1; i <=n; i++)cin>>a[i].v;
    //数组已经重新按疲劳值排好序列了。后面操作都是真对排好序的数组操作。
    sort(a+1,a+1+n,cmp);

    for (int i = 1; i <=n; i++) pre[i]=pre[i-1]+a[i].v; //最大的开始,前i项疲劳值之和
   
    for (int i = 1; i<=n; i++) preMax[i]=max(preMax[i-1],2*a[i].d); //前i项中,距离最大值                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 
    
    for (int i = n; i >=1; i--) last[i]=max(last[i+1],2*a[i].d+a[i].v); //后i项中,距离+疲劳值最大的。
        
    for(int i=1;i<=n;i++) cout<<max(pre[i]+preMax[i],pre[i-1]+last[i])<<endl;
    //取i个数,有两种取法,
    //一方案是按疲劳值取最大的i个数,再加上其中距离最远的哪个数的距离
    //二方案是按疲劳值取最最大的i-1个数,再加上按后i项中,距离+疲劳值最大的。
    //两种方案取最大值输出。              
}                                                                                                     
Scroll to Top