ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛 A Visiting Peking University

作者：笔触狂放9 | 2024-06-07 01:34:41

踩

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

最水的一个题，最简单的模拟，因为读错题等种种缘故，一直WA，见鬼，这种题都能错。

题意是一人去旅游N天，在北京待M天，他想去参观PKU，他知道这N天参观排队的人数，但是有Q天交通管制，哪都去不了。所以他决定待K天，但是有要求，在前K天中，只要有K-M天是交通管制时间，请注意，是K减M。他可以选择两天参观，问最少排队人数是多少，注意排队人数的下标是0—N-1，但管制天数是1—N，最后输出这两天。

代码实现：


#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#define ll long long
#define mset(a,x) memset(a,x,sizeof(a))
 
using namespace std;
const double PI=acos(-1);
const int inf=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1005;
const int mod=1e9+7;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll inv(ll b){if(b==1)return 1; return (mod-mod/b)*inv(mod%b)%mod;}
ll fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}
struct node{
	int x;
	int index;
}p[1000];
 
int main()
{
	int n,m,i,j,k,q,x;
	int map[maxn],visit[maxn];
	while(cin>>n>>m)
	{
		mset(visit,0);
		for(i=0;i<n;i++)
		cin>>map[i];
		
		cin>>q;
		for(i=0;i<q;i++)
		{
			cin>>x;
			visit[x]=1;
		}
		
		k=0;
		for(i=0;i<n;i++)
		{
			if(!visit[i])
			{
				p[k].x=map[i];
                p[k].index=i;
                k++;
			}
		}
		
		int minx,miny,minn=inf,temp,tempi;
		for(i=0;i<=k-m;i++)
		{
			temp=inf;
			for(j=1;j<m;j++)
			{
				if (p[i+j].x<temp)
				{
	                temp=p[i+j].x;
	                tempi=p[i+j].index;
	            }
			}
            if (temp+p[i].x<minn)
			{
                minn=temp+p[i].x;
                minx=p[i].index;
                miny=tempi;
            }
		}
		cout<<minx<<' '<<miny<<endl;
	}
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/683431