hihoCoder 1578 Visiting Peking University 【贪心】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hihoCoder 1578 Visiting Peking University 【贪心】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4215字,纯文字阅读大概需要7分钟。
内容图文
![hihoCoder 1578 Visiting Peking University 【贪心】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)](/upload/InfoBanner/zyjiaocheng/1051/d249ede7c6c74d0e978adfd84ac05df9.jpg)
#1578 : Visiting Peking University
时间限制:1000ms单点时限:1000ms内存限制:256MB描述
Ming is going to travel for n days and the date of these days can be represented by n integers: 0, 1, 2, …, n-1. He plans to spend m consecutive days(2 ≤ m ≤ n)in Beijing. During these m days, he intends to use the first day and another day to visit Peking university. Before he made his plan, Ming investigated on the number of tourists who would be waiting in line to enter Peking university during his n-day trip, and the results could be represented by an integer sequence p[i] (0 ≤ i ≤ n-1, p[i] represents the number of waiting tourists on day i). To save time, he hopes to choose two certain dates a and b to visit PKU(0 ≤ a < b ≤ n-1), which makes p[a] + p[b] as small as possible.
Unfortunately, Ming comes to know that traffic control will be taking place in Beijing on some days during his n-day trip, and he won’t be able to visit any place in Beijing, including PKU, on a traffic control day. Ming loves Beijing and he wants to make sure that m days can be used to visit interesting places in Beijing. So Ming made a decision: spending k (m ≤ k ≤ n) consecutive days in Beijing is also acceptable if there are k - m traffic control days among those k days. Under this complicated situation, he doesn’t know how to make the best schedule. Please write a program to help Ming determine the best dates of the two days to visit Peking University. Data guarantees a unique solution.
输入
There are no more than 20 test cases.
For each test case:
The first line contains two integers, above mentioned n and m (2 ≤ n ≤ 100, 2 ≤ m ≤ n).
The second line contains n integers, above mentioned p[0] , p[1] , … p[n-1]. (0 ≤ p[i] ≤ 1000, i = 0 ... n-1)
The third line is an integer q (0 ≤ q ≤ n), representing the total number of traffic control days during the n-day trip, followed by q integers representing the dates of these days.
输出
One line, including two integers a and b, representing the best dates for visiting PKU.
- 样例输入
7 3 6 9 10 1 0 8 35 3 5 6 2 4 2 10 11 1 2 1 2- 样例输出
0 3 1 3
题目链接:
http://hihocoder.com/problemset/problem/1578
题目大意:
n天旅游时间,小明打算花其中连续的m天去北京玩,其中第一天a和另外一天b去参观清华,
已知n天里参观清华排队的人数为p[i],目的是使得p[a]+p[b]最小。
又因为北京有q天交通管制,所以实际上可以花连续k天,使得k天中恰有k-m天是交通管制,剩余m天游玩。
题目思路:
【贪心】
首先分析题目发现,其实要找连续k天满足其中有m天没交通管制,且第一天和其中一天p之和最小即可。
k不固定,所以考虑将交通管制的天扣掉,这样找区间长度为m且满足p[a]+p[b]最小即可。
直接暴力枚举,记录b的位置。
然后将交通管制恢复,得到最终正确的答案。
![技术分享](/img/jia.gif)
![技术分享](/img/jian.gif)
1 /* *************************************************** 2 3 Author : Coolxxx 4 Copyright 2017 by Coolxxx. All rights reserved. 5 BLOG : http://blog.csdn.net/u010568270 6 7 *************************************************** */ 8 #include<bits/stdc++.h> 9#pragma comment(linker,"/STACK:1024000000,1024000000") 10#define abs(a) ((a)>0?(a):(-(a))) 11#define lowbit(a) (a&(-a)) 12#define sqr(a) ((a)*(a)) 13#define mem(a,b) memset(a,b,sizeof(a)) 14constdouble EPS=0.00001; 15constint J=10; 16constint MOD=1000000007; 17constint MAX=0x7f7f7f7f; 18constdouble PI=3.14159265358979323; 19constint N=104; 20usingnamespace std; 21 typedef longlong LL; 22double anss; 23LL aans; 24int cas,cass; 25int n,m,lll,ans; 26int a[N],b[N]; 27bool u[N]; 28int main() 29{ 30 #ifndef ONLINE_JUDGE 31// freopen("1.txt","r",stdin); 32// freopen("2.txt","w",stdout);33#endif34int i,j,k; 35int x,y,z; 36// for(scanf("%d",&cass);cass;cass--) 37// init(); 38// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)39while(~scanf("%d",&n)) 40 { 41 mem(u,0); 42 scanf("%d",&m); 43for(i=0;i<n;i++) 44 { 45 scanf("%d",&a[i]); 46 } 47 scanf("%d",&cas); 48for(i=1;i<=cas;i++) 49 { 50 scanf("%d",&x); 51 u[x]=1; 52 } 53for(i=0,j=0;i<n;i++) 54 { 55if(u[i])continue; 56 b[j++]=a[i]; 57 } 58 ans=MAX; 59for(i=0;i<=j-m;i++) 60 { 61for(k=i+1;k<min(i+m,j);k++) 62 { 63if(b[i]+b[k]<ans) 64 { 65 ans=b[i]+b[k]; 66 y=i;z=k; 67 } 68 } 69 } 70for(i=0;i<n;i++) 71 { 72if(u[i])continue; 73if(!y)break; 74 y--; 75 } 76 y=i; 77for(i=0;i<n;i++) 78 { 79if(u[i])continue; 80if(!z)break; 81 z--; 82 } 83 z=i; 84 printf("%d %d\n",y,z); 85 } 86return0; 87} 88/*89// 9091// 92*/
原文:http://www.cnblogs.com/Coolxxx/p/7611760.html
内容总结
以上是互联网集市为您收集整理的hihoCoder 1578 Visiting Peking University 【贪心】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)全部内容,希望文章能够帮你解决hihoCoder 1578 Visiting Peking University 【贪心】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。