钱多多嫁人记吻戏,zhz甄嬛传,葛守江
【问题描述】
阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住房。螺丝街一构有n 家住房，第i 家住户到入口的距离为si 米。由于同一栋房子里可以有多家住户，所以可能有多家住房与入口的距离相等。阿明会从入口进入，依次向螺丝街的x 家住房推销产品，然后再原路走出去。阿明每走1 米就会积累1 点疲劳值，向第i 家住房推销产品会积累ai 点疲劳值。阿明是工作狂，他想知道，对于不同的x,在不走多余路的前提下，他最多可以积累多少点疲劳值。
【输入格式】
第一行有一个正整数n，表示螺丝街住房的数量。
接下来的一行有n 个正整数，其中第i 个整数si 表示第i 家住户到入口的距离。数据保证s1≤s2≤…≤sn≤10^8。
接下来的一行有n 个整数，其中第i 个整数ai 表示向第i 户住户推销产品会积累的疲劳值。数据保证ai<10^3。
【输出格式】
输出n 行，每行一个正整数，第i 行整数表示当x=i 时，阿明最多积累的疲劳值。
我见过noip t4最水的题，没有之一。
这道题算法为贪心（废话），但应该怎么贪呢？
首先，通过我们分析可得，最大值一定是取x个最大值+2*已取数的最大距离或x-1个最大值+2*所有数的最大距离+最远且最大的数。所以需要三个数组，sum（前x个数的总和），maxlen（前x个数最远距离），h（2*所有数的最大距离+最远且最大的数）
我要评论 1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,sum[100005],maxlen[100005],h[100005];
4 struct node{int s,a;}x[100005];
5 bool cmp(node p,node q)
6 {
7 return p.a>q.a;
8 }
9 int main()
10 {
11 cin>>n;
12 for (int i=1;i<=n;i++) cin>>x[i].s;
13 for (int i=1;i<=n;i++) cin>>x[i].a;
14 sort(x+1,x+n+1,cmp);
15 for (int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i].a;
16 for (int i=1;i<=n;i++) maxlen[i]=max(maxlen[i-1],x[i].s);
17 for (int i=n;i>=1;i--) h[i]=max(h[i+1],x[i].s*2+x[i].a);
18 for (int i=1;i<=n;i++) cout<<max(sum[i]+2*maxlen[i],sum[i-1]+h[i])<<endl;
19 return 0;
20 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论