题解 P6015 【游戏】

· · 题解

设 a_i 的前缀和为 s_i，小 Z 取走了前 p 张牌，小 Y 和小 Z一共取走了 q 张牌。

则小 Z 的点数为 z=s_p，小 Y 的点数为 y=s_q-s_p。

小 Y 为了自己不输，他的点数不能小于小 Z 的点数，但也不能太大（超过上限就不划算了）。最理想的情况是，小 Y 如果少取一张牌，他的点数就小于小 Z 了。

在这种情况下，为了能让小 Z 胜出，只需让上限 x 小于 y 就行。

现在问题是对于每个 p，我们需要找到相应的 q，找到了 q，y 就算出来了。

可以二分找，时间复杂度是 O(n \log n) 的。

更快的方式是双指针，即移动 p 的时候，同时将 q 向右移动，直到 q 到达我们需要的位置。时间复杂度为 O(n)，比二分的方法更优。

下面是笔者在比赛时写的 O(n \log n) 的二分做法。

#include <iostream>
using namespace std;
long long a[1000005],res[1000005];
int main()
{
 ios::sync_with_stdio(false);
 int n,k,ans=0;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i];
  a[i]+=a[i-1];
 }
 cin>>k;
 for(int i=1;i<=n;i++)
 {
  if(a[i]>=k)break;
  int p=lower_bound(a+1,a+n+1,2*a[i])-a;
  if(p==n+1||a[p]-a[i]>k)
  {
   res[a[i]]++;
   res[k+1]--;
   break;
  }
  res[a[i]]++;
  res[a[p]-a[i]]--;
 }
 for(int i=1;i<=k;i++)
 {
  res[i]+=res[i-1];
  if(res[i])ans++;
 }
 cout<<ans<<endl;
 for(int i=1;i<=k;i++)
  if(res[i])cout<<i<<' ';
 return 0;
}