快手笔试-健身

输出N行, 第K行表示选择K种方式能获得最大的值

样例

输入:

1 2 3 4 5

1 1 1 1 1

输出:

说明: N<=1e5

题意从出口到终点再返回, 选择k种锻炼方式, 其中终点的锻炼方式一定要选的. 所获得的最大值

分析: 这是一道贪心题, 笔试没有做来. 最后还是静下来才思考出来的

假使选择K种方式获取最大值的方式是ak1, ak2, ak3, ak4

有这样的性质:ak1,ak2,ak3是[1,k4)区间的最的三个值

那么选择三个的话, 只有这两种方式:

(1) 不选ak4, ak1,ak2,ak3

(2) 选择ak4, ak1,ak2,ak3; 选择去掉一个最小值

可以用反正发证明其他方式不是最优的

那么我们就需要维护这两个值

// 我描述能力不行....再过一段时间再来看看这个代码把,

// 太菜了....加油啊....

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+7;
 4 struct node {
 5     int d,val;
 6     int id;
 7 };
 8 node t1[N],t2[N];
 9 int dp[N]; bool vis[N]; 
10 int n,sum;
11 bool cmp1(node a, node b) {
12     return a.d<b.d;
13 }
14 bool cmp2(node a, node b) {
15     return a.val<b.val;
16 }
17 int main()
18 {
19     scanf("%d",&n);
20     for (int i=1;i<=n;i++) 
21         scanf("%d",&t1[i].d);
22     for (int i=1;i<=n;i++) {
23         scanf("%d",&t1[i].val);
24         sum+=t1[i].val;
25     }
26     sort(t1+1,t1+1+n,cmp1);
27     for (int i=1;i<=n;i++) {
28         t2[i]=t1[i];
29         t2[i].id=i;
30     }
31     sort(t2+1,t2+1+n,cmp2);
32     dp[n]=sum+t1[n].d*2;
33     int k1=n,pos=1;
34     for (int i=n-1;i>=1;i--) {
35         int k2=k1-1;
36         while (vis[k2]) k2--;
37         while (t2[pos].id>=k1) pos++;
38         int v1=dp[i+1]-t1[k1].d*2-t1[k1].val+t1[k2].d*2;
39         int v2=dp[i+1]-t2[pos].val;
40         if (v1>v2) {
41             dp[i]=v1;
42             k1=k2;
43         }
44         else {
45             dp[i]=v2;
46             vis[t2[pos].id]=1;
47             pos++;
48         }
49         //cout<<k1<<endl;
50     }
51     for (int i=1;i<=n;i++)
52         printf("%d
",dp[i]);
53     return 0;
54 }