专栏文章

题解:CF508C Anya and Ghosts

CF508C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq93wii
此快照首次捕获于
2025/12/04 00:58
3 个月前
此快照最后确认于
2025/12/04 00:58
3 个月前
查看原文

CF508C 题目传送门

题目大意

夜市中管理方会在午夜后进行 mm 次检查,第 ii 次检查在午夜后的第 wiw_i 秒进行,每次检查持续 11 秒钟,要求每次检查夜市里至少有 rr 根蜡烛在燃烧。已知每根蜡烛能燃烧 tt 秒,点燃一根蜡烛需要 11 秒。你的任务是要使每次检查都合格,最少需要多少根蜡烛。

解决思路

首先考虑特殊情况,即输出 1-1。如果每根蜡烛燃烧的时间小于最小的蜡烛根数(t<rt < r),即不满足要求,则直接输出 1-1。每次鬼魂到达时,检查之前点燃的蜡烛是否还能覆盖当前时间。如果不能,就点燃新蜡烛。最后输出总共点燃的蜡烛数量。

代码展示

CPP
#include <iostream>
using namespace std;
 
int m, t, r, w, a[1010];
//a[]表示燃烧的蜡烛的结束时间 
int x, y, ans;
//x表示燃烧的蜡烛的起始下标 
//y表示下一个要被点燃的蜡烛下标

int main() 
{
	cin >> m >> t >> r;
	if(t < r) 
	{//如果每根蜡烛燃烧的时间小于最小的蜡烛根数,
		puts("-1");//即不满足情况,则直接输出-1
		return 0;
	}
	for(int i = 1; i <= m; i++)
	{
		cin >> w;
		while(x < y && a[x] < w) x++;
		for(int j = w - r + y - x; j < w;j++)
		{
			a[y++] = j + t;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...