D.Extreme Subtraction
題目傳送門：
Extreme Subtraction
題目大意：
有一個長度為n的陣列a，你可以進行無數次如下操作：
- a1~ai 減1
- ai~an減1
問能否使陣列中的元素全部變成0；
思路：
轉化成一個差分問題，(假設差分陣列為ans)要使陣列中的全部數都為0，那么差分陣列也必須為0且ans[1]=0，
那么我們來看兩種操作對于差分陣列有何影響：
操作1：ans[1]-1 且ans[i+1]+1，那么我們就可以憑借操作1，將差分陣列中的負數變成0，同時減小ans[1]，
操作2：ans[i+1]-1且ans[n+1]+1，那么我們就可以憑借操作2，將差分陣列中的正數變成0，而ans[n+1]為多少和我們并沒有關系，
在最開始時ans[1]=a[1]，所以只要差分陣列的負數和的絕對值小于等于a[1],即輸出YES，否則輸出NO，
因為如果差分陣列的負數和的絕對值大于a[1],那么要使后面的數都變成0，ans[1]就會變成負數，而并沒有使ans[1]由負數變成0的操作，操作2只能使ans[1]由正數變成0，所以這樣并不滿足要求，
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int a[N];
int ans[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
a[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ans[i]=a[i]-a[i-1];
}
int res=0;
for(int i=2;i<=n;i++)
if(ans[i]<0) res=res+(-1)*ans[i];
if(res<=a[1]) printf("YES\n");
else printf("NO\n");
}
//system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/202551.html
標籤：其他
上一篇：23歲的我，從阿里JAVA面試后的總結與反思，希望這些領悟還不晚
下一篇：打包Chrome的插件擴展程式