2020.5.23 Nordic Collegiate Programming Contest 2015 prob:7/7/10 rank:1/29

本周无

本周无

林星涵：

陶吟翔：

郭衍培：题目链接

给定长度为n的数列，保证后$\lfloor \frac n2 \rfloor$个数是相同的。求一个k，使得任意连续k个数的和都大于0，若不存在输出-1

显然，如果数列的总和大于0，则只需要取k=n即可。如果数列总和小于等于0，而后$\lfloor \frac n2 \rfloor$个数大于等于0，则一定不存在满足要求的k（否则取若干个连续k项加末尾若干个数，得到数列总和大于0）。 因此，只需解决数列总和小于0，且最后$\lfloor \frac n2 \rfloor$个数小于0的情况。此时，显然有$k>\lfloor \frac n2 \rfloor$ 记录前$\lceil \frac n2 \rceil$个数的后缀和，并计算以i为起始，和为正的最大长度$l_i$。记录$k_m=\min_{i=1}^m{l_i}$，直到第i项，有$i+k_i>n$，则$k_i$满足要求，否则不存在满足要求的解。