current position:Home>B. Luke is a Foodie (greedy/simulation)

B. Luke is a Foodie (greedy/simulation)

2022-08-06 09:24:03Luo gkv

题目

题意

给定npile of food,Each pile of food has a deliciousnessa[i],吃第ipile of food,Ask for the current taster's tastev,与它的a[i]The absolute value cannot be exceededx,即|a[i]-v|<=x.
Tasters eat these foods from left to right,Ask him how many adjustments are required at leastv,to eat all the food.
first setv可以取任意值,And not as the number of adjustments.

思路

从左到右,Simulate to take the left and right boundaries of the acceptable taste of each food.

  • If you can't eat it,Just open a new onev,次数+1.
  • If you can eat it,则更新,For the left and right borders of the current food set 交集.

详见代码.

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;

int n, x;
int a[maxn];
void solve() {
    
	scanf("%d%d", &n, &x);
	for (int i = 0; i < n; ++i) {
    
		scanf("%d", &a[i]);
	}
	
	int count = 0, l = a[0] - x, r = a[0] + x;
	for (int i = 1; i < n; ++i) {
    
		int tmpl = a[i] - x, tmpr = a[i] + x;
		if (r < tmpl || tmpr < l) {
    
			++count;
			l = tmpl;
			r = tmpr;
		} else {
    
			l = max(l, tmpl);
			r = min(r, tmpr);
		}
	}
	printf("%d\n", count);
}
int main() {
    
	int t;
	scanf("%d", &t);
	while (t--) {
    
		solve();
	}
}

最后

weixin gongzhonghao搜 对方正在debug,关注下,一起快乐刷题吧~

copyright notice
author[Luo gkv],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060918144584.html

Random recommended