自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:16:33，当前版本为作者最后更新于2020-01-28 19:12:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $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;
}