CodeForces - 1443D Extreme Subtraction 差分应用-白红宇的个人博客

CodeForces - 1443D Extreme Subtraction 差分应用

发布日期：2021-05-10 11:28:57 浏览次数：18 分类：精选文章

本文共 2286 字，大约阅读时间需要 7 分钟。

��

����

�� diff�� diff[i] = a[i] - a[i-1]��1 �� i < n��

��diff[n+1] = -a[n]��

����

�� diff[i] < 0��

�� diff[n+1] ��

����

�� diff ��

�� sm�� diff[n+1] ��

����

�� sm �� diff[n+1]��

��

����

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
#include 
        
          #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl "\n" using namespace std; typedef long long ll; const int maxn = 30500; const int inf = 0x3f3f3f3f; int n, m; int a[maxn]; int diff[maxn + 1]; // diff[n+1] ������������ int main() { IOS int tn; cin >> tn; while (tn--) { bool possible = true; cin >> n; a[n] = 0; for (int i = 1; i <= n; i++) { int val; cin >> val; a[i] = val; } diff[1] = a[1]; for (int i = 2; i <= n; i++) { diff[i] = a[i] - a[i-1]; } diff[n+1] = -a[n]; // ������������������������0 bool handled_negative = false; for (int i=2; i<=n+1; i++) { if (diff[i] < 0) { if (!handled_negative) { diff[1] += diff[i]; diff[i+1] -= diff[i]; handled_negative = true; } else { // ��������������������������������������������������������� diff[1] += diff[i]; diff[n+1] -= diff[i]; } } } // ������������������������������ int sm = 0; for(int i=2; i<=n; i++) { if(diff[i] > 0) { sm += diff[i]; } } if(sm <= diff[n+1]) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; }

����

上一篇：最小环问题总结（有向，无向，经过某一点）

下一篇：导弹防御系统 ACwing187 最长上升/下降子序列+贪心+DFS

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章