dtcms插件 微信商家收款 Jenkins dataframe keras autocomplete compilation mono air 河南普通话考试 php零基础入门视频 jquery循环遍历 jquery使用ajax oracle删除表字段 pip环境变量配置 ubuntu查看python版本 vue使用bootstrap java解析pdf python语言编程入门 python当前日期 python正则替换 java实现接口 java方法重载 java获取当前线程 java时间转换 java输出数组 java取当前时间 java怎么学 VSPD 保留小数点后两位 spss20安装教程 layout下载 编程电子书 分屏软件 红米手机怎么连接电脑 模拟邻居 lol无限视野 ipad怎么清理内存垃圾 倒计时定时器 画图3d
当前位置: 首页 > 学习教程  > 编程语言

CodeForces - 1468D - Firecrackers

2021/2/13 20:04:42 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Firecrackers 题意 一个囚犯和一个守卫 在一维坐标上移动,每一秒按顺序发生以下三件事 囚犯向左或向右移动一步 或者呆在原地, 如果囚犯呆在原地, 那么它可以在所处的位置放下一个鞭炮 一些鞭炮可能会爆炸 对于第 iii 个 鞭炮 会在被放置后…

Firecrackers

题意

一个囚犯和一个守卫 在一维坐标上移动,每一秒按顺序发生以下三件事

  1. 囚犯向左或向右移动一步 或者呆在原地, 如果囚犯呆在原地, 那么它可以在所处的位置放下一个鞭炮

  2. 一些鞭炮可能会爆炸 对于第 i i i 个 鞭炮 会在被放置后的 s i s_i si 秒爆炸

  3. 守卫会朝囚犯的方向前进一步

    问:在囚犯被守卫捉住前 最多能爆炸多少鞭炮

思路

首先要知道 一个格子可以同时存在多个鞭炮… 一开始没注意到这一点死活解不出来

其次 先放鞭炮再跑 和先跑再放鞭炮,肯定是前者更优,因为在跑的过程中,鞭炮已经在倒计时了,所以我们可以让囚犯在没被逮到之前一直处于出生点,然后不断地放鞭炮,直到守卫到他旁边一格,以 b > a b > a b>a 为例 ( a > b a > b a>b 同理),一共最多可以放 a b s ( b − a ) − 1 abs(b - a) - 1 abs(ba)1 个鞭炮 然后囚犯可以向守卫来的反方向逃跑最多 a − 1 a - 1 a1 秒 用 t o t tot tot 表示当前距离囚犯被抓还有几秒 如果鞭炮的 s i s_i si 小于等于当前的 t o t tot tot 则可以爆炸,因为放下鞭炮需要 1 1 1 秒 所以更新 t o t − − tot-- tot

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
using namespace std;

typedef  long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
const int N = 200010;

LL n, m, a, b;
LL c[N];

bool cmp(LL a, LL b) {
	return a > b;
}

void solve() {
	scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
	
	for (int i = 1; i <= m; ++i)scanf("%lld", &c[i]);

	sort(c + 1, c + m + 1, cmp);

	int tot = a - 1;
	if (a > b)tot = n - a;

	int boom = abs(b - a) - 1;
	tot += boom;

	int cnt = 0;
	for (int i = 1; i <= m; ++i) {
		if (cnt == boom)break;

		if (c[i] <= tot) {
			cnt++;
			tot--;
		}
	}
	cout << cnt << endl;
}

int main() {
	int t; cin >> t;
	while(t--)
		solve();

	return 0;
}


本文链接: http://www.dtmao.cc/news_show_700385.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?