LG-P1311选择客栈
2018-10-29 15:26:29来源:博客园 阅读 ()
题目
暴力十分好想但你写不出来qwq
正解十分好写但你想不出来qaq
我们先读题,发现k其实没什么用
同时暴力枚举两个客栈的话会超时,所以只能同时枚举一个。我们枚举第二个客栈,然后用第二个客栈反推出前面的方案数。
思路就是,从1到n枚举,输入颜色color和价钱price,我们需要记录一个距离第二个客栈最近且价钱合理(小于等于p)的咖啡厅的客栈位置,用变量now记录。
然后开三个辅助数组,last[i]表示最后一个以i为颜色的客栈的位置,cnt[i]表示以i为颜色的客栈总数,sum[i]可以看作是一个临时数组,用来存储当前的方案数。
可以这么想,当前枚举到一个客栈i,这个i是第二个客栈,那么显然第一个客栈一定在第二个客栈之前,编号必定是0~i-1之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅,那么在这之前的任何一个同色客栈都是第一个客栈可以选的,那么统计一下数量,这就是当前的方案数。
然后更新last数组,更新ans,让cnt[color]++,这样从左到右地推过来就好了。
这个解法简化于暴力算法,暴力算法要循环三层,一层1客栈,二层2客栈,3层合理的位置,这样做显然不行,而我们做的就是去优化掉两层,从枚举2客栈出发推出1客栈的位置和所有可行方案,所以这样做是正确的。最后输出即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 int n,k,p; 8 int color,price,now,ans; 9 int last[55],sum[55],cnt[55]; 10 11 int main() 12 { 13 ios::sync_with_stdio(false);//关同步,让你的cin,cout快过scanf,printf! 14 cin>>n>>k>>p; 15 for(int i=1; i <= n; i++){ 16 cin>>color>>price; 17 if(price <= p) 18 now=i; 19 if(now >= last[color]) 20 sum[color]=cnt[color]; 21 last[color]=i; 22 cnt[color]++; 23 ans += sum[color]; 24 } 25 cout<<ans<<"\n";//\n比endl快8倍 26 return 0; 27 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:福州大学算法作业题 - 加法运算
下一篇:队列之士兵报数
- 自定义日历(四)-区间选择控件 2019-11-02
- 单链表的选择排序 2019-09-17
- 选择排序的理解 2019-08-16
- 堆排序 2019-08-16
- QTableView表格控件区域选择-自绘选择区域 2019-08-16
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