B. Luke is a Foodie（贪心/模拟）

题目

题意

给定n堆食物，每堆食物有美味度a[i]，吃第i堆食物，要求当前的品尝者的品尝度v，与它的a[i]绝对值不能超过x，即|a[i]-v|<=x。
品尝者从左到右去吃这些食物，问他最少需要调整多少次v，才能吃完所有食物。
第一设定的v可以取任意值，且不做为调整的次数。

思路

从左到右，模拟去取每个食物可以接受美味度的左右边界。

• 如果吃不了的，就只能新开一个v，次数+1。
• 如果吃得了的，则更新，当前食物集合的左右边界的 交集。

详见代码。

代码

#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，关注下，一起快乐刷题吧~