NOIP2015 T4 推销员
2018-08-26 17:16:51来源:博客园 阅读 ()
题面
【问题描述】
阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住房。螺丝街一构有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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:ZOJ 3203 灯泡
下一篇:浅谈c++中的KMP
- 「BZOJ4173」数学 2020-01-15
- 【CSP-S膜你考】 A 2019-10-17
- 【NOIP2015普及组】 推销员(纪中数据-标准) 2019-08-16
- P2670 【扫雷游戏】 2019-08-16
- 洛谷 P2678 & [NOIP2015提高组] 跳石头 2019-04-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash