嗨嗨嗨

全部评论 1

• 

  zyy

  

  删除

  #include <bits/stdc++.h>
  #define fo(a,b,c) for (a=b; a<=c; a++)
  #define fd(a,b,c) for (a=b; a>=c; a--)
  #define ll long long
  #define file
  using namespace std;
  struct type
  {
  int s,x;
  } s1,s2;
  struct Queue
  {
  type d[1000001];
  int h,t;
  void push(type s)
  {
  d[++t] = s;
  }
  void pop(bool tp)
  {
  if (!tp)
  {
  ++h;
  }
  else
  {
  --t;
  }
  }
  void clear()
  {
  h = 1,t = 0;
  }
  bool empty()
  {
  return h > t;
  }
  type head()
  {
  return d[h];
  }
  type tail()
  {
  return d[t];
  }
  } q[2];
  int a[1000001],T,n,i,j,k,l,I,x,y,ans,I1,I2,sum;
  bool operator < (type a,type b)
  {
  return a.s < b.s || a.s == b.s && a.x < b.x;
  }
  bool operator > (type a,type b)
  {
  return a.s > b.s || a.s == b.s && a.x > b.x;
  }
  void swap(int &x,int &y)
  {
  int z = x;x = y;y = z;
  }
  int main(void)
  {
  scanf("%d",&T);
  fo(I,1,T)
  {
  if (I == 1)
  {
  scanf("%d",&n);
  fo(i,1,n) scanf("%d",&a[i]);
  }
  else
  {
  scanf("%d",&k);
  fo(i,1,k) scanf("%d%d",&x,&y),a[x] = y;
  }
  q[0].clear(),q[1].clear(),ans = n;
  I1 = 0,I2 = 1;
  fd(i,n,1) q[I1].push(type{a[i],i});
  while (ans > 1)
  {
  --ans;
  if (q[I2].empty() || q[I1].tail() < q[I2].tail())
  {
  s2 = q[I1].tail(),q[I1].pop(1);
  }
  else
  {
  s2 = q[I2].tail(),q[I2].pop(1);
  }
  if (!s2.s)
  {
  continue;
  }
  if (q[I2].empty() || q[I1].head() > q[I2].head())
  {
  s1 = q[I1].head(),q[I1].pop(0);
  }
  else
  {
  s1 = q[I2].head(),q[I2].pop(0);
  }
  s1.s -= s2.s;
  if (q[I1].empty())
  {
  swap(I1,I2);
  }
  q[I2].push(s1);
  if (q[I1].tail() > s1)
  {
  break;
  }
  }
  if (ans > 1)
  {
  sum = 0;
  while (sum < ans - 1)
  {
  if (q[I2].empty() || q[I1].tail() < q[I2].tail())
  {
  s2 = q[I1].tail(),q[I1].pop(1);
  }
  else
  {
  s2 = q[I2].tail(),q[I2].pop(1);
  }
  if (q[I2].empty() || q[I1].head() > q[I2].head())
  {
  s1 = q[I1].head(),q[I1].pop(0);
  }
  else
  {
  s1 = q[I2].head(),q[I2].pop(0);
  }
  s1.s -= s2.s;
  if (q[I1].empty())
  {
  swap(I1,I2);
  }
  if (!q[I1].empty() && q[I1].tail() < s1 || !q[I2].empty() && q[I2].tail() < s1)
  {
  break;
  }
  q[I2].push(s1);
  ++sum;
  }
  sum += sum == (ans - 1);
  ans += !(sum&1);
  }
  printf("%d\n",ans);
  }
  fclose(stdin);
  fclose(stdout);
  }

  2024-12-03 来自 北京

  0