codeforces 1443 problem D
題目鏈接
題目大意：給你一個長度為n序列，你可以進行無數次操作，讓前k個數減一或讓后k個數減一，1<=k<=n,問是否能把這整個序列變為0序列，
（我是傻逼，沒有初始化，太菜了，比賽的時候沒有做出來QAQ ）
寫題時要找好清晰的思路
8
252 210 750 818 640 868 700 777
首先可以確定，如果一個數能被減小，他能減少的數值一定不會超過他之前能被減少的數值
比如上面那個例子，750絕對不可能變成比540還小的數，如果繼續變的話第二個數就會變成負數
第二，他被減完后的數一定是要大于前面的數的，不然從后往前減的時候，前面那個數就不會變成0
比如818->608之后,640->430，在從后往前篩時608這個數是一定不能變為0的，所以640只能變為608
所以我們發現接下來的數最多也就只能減32的所以能被減的數是不斷變小的
如果經過從前往后篩和從后往前篩都不能讓這個序列變為0，那么這個序列就是不好的，否則就是好的
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
const int maxn=2e6+10;
#define inf 9999969
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define fep(i,a,b) for(int i=b;i>=a;--i)
#define scf(x) scanf("%lld",&x)
#define prf(x) printf("%lld\n",x)
#define deprf(x) printf("[%lld]\n",x)
#define mymset(x,y) memset(x,y,sizeof(x))
const int mod=9901;
using namespace std;
ll a[maxn];
int main()
{
ll t,n;
scf(t);
while(t--)
{
scf(n);
rep(i,1,n)scf(a[i]);
ll lala=a[1];//這個lala存的是改變前和改變后的最小差值
a[0]=0,a[n+1]=0;
rep(i,1,n)
{
ll p=a[i];
if(a[i])a[i]=max(max(0LL,min(a[i-1],a[i])),a[i]-lala);//改變后不能超過前面的數
//且不能小于0
else break; //如果能減最大只能減前面的最小差值
if(p==a[i])break;//如果這個數沒有發生改變證明接下來的數也就不能被減了
lala=min(lala,p-a[i]);//更新最小差值
}
lala=a[n];
fep(i,1,n)//從后往前跟從前往后是一樣的
{
ll p=a[i];
if(a[i])a[i]=max(max(0LL,min(a[i+1],a[i])),a[i]-lala);
else break;
if(p==a[i])break;
lala=min(lala,p-a[i]);
}
int f=0;//答案標記
rep(i,1,n)if(a[i])f=1;//查看是否有數不為0
if(f)printf("NO\n");
else printf("YES\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/204189.html
標籤：其他
上一篇：經典三子棋小游戲（C語言版）