2020-11-13牛客挑战赛45-A

[by_041]

• 这道题首先引起我注意的是：偶数，最值等关键词

• 于是我的第（tian）一（zhen）个（de）反应是开数组，筛奇数，排序

• 然后因为每次操作是在原来的基础上减掉最大偶数的一半，所以只要预存下原来所有数的sum后剪掉砍掉的偶数的一半就行

• 本来是想按步插入排序的，但是很明显数级的操作会超时

• 这时候就要考虑自动有序的优先队列了

• 然后DEBUG了数次，用血与泪总结出了以下一点：

  • 数据范围决定数据类型：

• 我果然是太久没打了嘛😭

• 下面附上AC代码：

  #include<iostream>
  #include<queue>
  
  using namespace std;
  
  priority_queue<unsigned long long>my;
  
  unsigned long long n,k,j,jj,sum,a;
  
  int main()
  {
      scanf("%lld %lld",&n,&k);
      for(int i=1;i<=n;sum+=a,i++)
          {
              scanf("%lld",&a);
              if(a&1)
                  continue;
              my.push(a);
          }
      while(my.size()&&k--)
          {
              sum-=(j=(my.top()>>1));
              my.pop();jj=my.top();
              while(k&&j>jj&&(j&1)==0)
              {
                      j>>=1;
                      k--;
              }
              if(j&1)
                  continue;
              my.push(j);
          }
      printf("%lld",sum);
      return 0;
  }