1443D Extreme Subtraction

题目链接

题意

给定一个含有n个正整数的数组a

可以对a进行以下两种操作

  1. 将数组的前k位减1
  2. 将数组的后k位减1

问在经历了有限次操作之后能否使数组全部变为0

数据范围:1≤n≤30000,1≤ a i a_i ai 1 0 6 10^6 106

思路

首先,如果可以使a变为一个均为非负数的非递减数列,就可以可以使数组全部变为0
那么问题就转变为了将a变成均为非负数的非递减数列

记录数组中第一位的数字first、当前位置的数cur和当前位的前一位front,如果front-cur 0,就将当前位之前的所有数字减去front-cur个1(不包括当前位)。
遍历整个数组之后,如果first=0,就可以确保可以使数组全部变为0

AC的代码
#include bits/stdc++.h
using namespace std;

int first, front, cur;

int main() {
	int t;
	cin  t;
	while (t--) {
		int n;
		cin  n  front;
		first = front;
		for (int i = 2; i = n; i++) {
			cin  cur;
			// front为上一个cur
			first -= max(front - cur, 0);
			front = cur;
		}

		cout  (first = 0 ? "YES\n" : "NO\n");
	}
	return 0;
}
演示步骤: 原数组
a[0]a[1]a[2]a[3]a[4]
117968

前1位减去3个1

a[0]a[1]a[2]a[3]a[4]
37968

前3位减去3个1

a[0]a[1]a[2]a[3]a[4]
04668
最新回复(0)
/jishu2nLY7NiyILaCSksFNobwMTbjWvzfF4QaCsVlRQ_3D_3D4794947
8 简首页