#C241111A. 切割蛋糕
标签（Label）
- 数学
- 思维
网址（Website）
题目（Problem）
题解（Solution）
$\qquad$这更像一道猜结论题。
$\qquad$发现这道题和平均数有关，直接求出全局平均数 $\overline{a}$ ，发现 Alice 和 Bob 占有整块蛋糕，所以容易发现如果 Alice 的平均数大于整体平均数，Bob 的平均数一定更小。
$\qquad$断环成链，求出前缀和 $c_i$ ，发现对于一个起始点 $i$ ，能满足条件当且仅当 $\forall j\in[i+1,i+n-1],\frac{c_{j-1}-c_i}{j-i}\ge \overline{a}$ ，发现这个平均数很麻烦，干脆对所有 $a_i$ 都减去 $\overline{a}$ ，让平均数变为 $0$ ，就只需要判断 $\forall j\in[i+1,i+n-1],c_{j-1}\ge c_i$ ，所以对于 $i$ ，只要 $\exists j\in[i+1,i+n-1],c_{j-1}<c_i$ ，当前 $i$ 就不行，很明显只要找到最小的那个 $c_i$ ，Alice 就一定能胜利，有多个最小值就选第一个就行了。
$\qquad$时间复杂度： $O(n)$ 。
出题者题解
算法分析
首先进行如下转化：令所有数字的平均数是 $S$，若 Alice 拿到的数字平均数大于等于 $S$，则 Alice 获胜。于是可以令 $a_i’ = a_i - S$，我们就变成要求 Alice 拿到的数字大于等于 $0$ 即可。
考虑一个这二维平面上的折线 $(i, sum_i)$，其中 $sum_i$ 是 $a’$ 的前缀和，由于 $sum_n’ = 0$。问题就变成了 Alice 选则一个点，Bob 选择一个在 Alice 后面的点，能否比 Alice 选的点的 $y$ 坐标小。因此 Alice 只能选 $sum_i$ 的最小值的点，如果有多个，根据题意需要选第一个。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i++)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
int a[N],c[N];
int n,sm;
inline int calc(int l,int r){return c[r]-c[l-1];}
void Solve(){
n=rd();For(i,1,n) a[i]=rd();
For(i,1,n) c[i] = c[i-1]+a[i];
For(i,1,n) c[i] = c[i]*n-c[n]*i;
printf("%lld\n",min_element(c+1,c+n+1)-c+1);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
int Tt=1;double Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
