贪心_P1739_N诺计算机考研

all-clear

TA的个人主页 >

文章

粉丝

409

获赞

访问

52.1k

贪心

all-clear

P1739 华东师范大学2020年机试题

发布于2020年7月14日 23:29

阅读数 12.3k

思路：计算所有未被照亮的米所需要的灯数量。

#include<iostream>
#include<vector>

using namespace std;


int main()
{
	int n,m,k;
	while(cin>>n>>m>>k)
	{
		vector<int> pos(m);
		for(int i=0;i<m;i++)
		{
			cin>>pos[i]; 
		}
	
		
		int s = 1,ans = 0,r = 2*k+1;
		
		for(int i=0;i<m;i++)
		{
			int e = pos[i]-k;
			if(e > s)
				ans += (e-s)/r + ((e-s)%r!=0);	
			s = pos[i] + k + 1;
		}
		
		if( n + 1 > s)
			ans += (n+1-s)/r + ((n+1-s)%r!=0);
		
		cout<<ans<<endl;
	}
}

题意里有个坑，照亮（第）X-K米到（第）X+K实际上是2K+1的距离。

登录查看完整内容

登录后发布评论

2 条评论

randy

2021年9月2日 16:47

怎么会是2*K+1呢画图还是2*K啊

XXX777 : 回复 randy：这题本身就有问题，题意模糊不清。我理解的题意是长度为n的路，n+1个点(0~n)，然后使得每个间隔都要被照亮。但他写的这个，似乎长度为n就是n个点(1~n)，而且只需要确保每个点被照亮而不是每个间隔。

2021年9月6日 00:24