题目传送门：http://codeforces.com/problemset/problem/97/C
题意：给出$n$与一个范围在$[0,1]$内的递增序列$P_0-P_n$，试构造一个无穷序列$\{a_i\}$满足$0 \leq a_i \leq n$，使得对于任意$k > 0$满足$a_k \leq \sum\limits_{i=1}^{k-1}(n - 2a_i)$且极限$\lim\limits_{m \rightarrow +\infty} \frac{\sum\limits_{i=1}^mp_{a_i}}{m}$达到最大，给出这个最大值。$N \leq 100$
因为数列无限，所以显然不能够将这个数列表示出来，故考虑构造一个循环节，使这个循环节的平均值最大，然后无限循环这个循环节，就能够得到最大的平均值。所以我们考虑找到一个有限数列使得其平均值最大。
方法一：
考虑转换模型。令$Q=\sum\limits_{i=1}^{k-1}(n - 2a_i)$，对于$a_k$，它会造成$P_{a_k}$的贡献并使得$Q+=n-2a_k=-a_k+(n-a_k)$，也就是待选的范围$Q$减掉了$a_k$，又补上了$n-a_k$。故考虑：最开始我们有一个箱子，其中有$0$个物品，第$i$次从箱子中拿出$a_i$个物品，并补进$n-a_i$个物品，求$\lim\limits_{m \rightarrow +\infty} \frac{\sum\limits_{i=1}^mp_{a_i}}{m}$的最大值。
接下来我们能发现某一个时刻的决策只与其对应的$Q$有关，与时刻无关，所以我们可以将$Q$的取值看成点，决策转换看成边，边权是对应的贡献，构出一个图。可以知道其中对应箱子中物品数量大于$2n$的点显然是没有意义的，因为从其中取出$n$个得到$P_n$的贡献仍然能够覆盖所有的$0-n$的取值。所以我们的点数只有$2n$个（$0$点也是没有意义的，因为最优解一定不会出现在$0$号点）。
回到我们需要求的东西，是一个循环节，对应在图中是一个环。所以我们需要找的是图上一个平均边权最大的环。这个显然是可以二分的，check函数将所有边权减掉mid，用spfa判断正环即可。时间复杂度约为$O(N^3)$
#include<bits/stdc++.h>
#define R register
#define MAXN 100010
#define eps 1e-9
using namespace std;
] , dis[];
short N , K;
queue < int > q;
struct Edge{
int end , upEd;
double w;
}Ed[MAXN];
] , flo[] , cntEd;
];
inline void addEd(int a , int b , double c){
Ed[++cntEd].end = b;
Ed[cntEd].w = c;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
inline bool check(double mid){
while(!q.empty())
q.pop();
memset(dis , 0xdd , sizeof(dis));
memset(inq , , sizeof(inq));
memset(flo , , sizeof(flo));
dis[flo[] = ] = ;
q.push();
while(!q.empty()){
int t = q.front();
q.pop();
inq[t] = ;
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(dis[Ed[i].end] < dis[t] + Ed[i].w - mid){
dis[Ed[i].end] = dis[t] + Ed[i].w - mid;
flo[Ed[i].end] = flo[t] + ;
if(flo[Ed[i].end] > K)
;
if(!inq[Ed[i].end]){
inq[Ed[i].end] = ;
q.push(Ed[i].end);
}
}
}
;
}
inline void solve(){
; i <= K ; i++)
; j <= K ; j++){
int k = i - j;
) == (N & ))
addEd(i , j , p[N + i - j >> ]);
}
, r = ;
while(r - l > eps){
;
check(mid) ? l = mid : r = mid;
}
printf("%.8lf" , l);
}
int main(){
scanf("%d" , &N);
K = N << ;
; i <= N ; ++i)
scanf("%lf" , &p[i]);
solve();
;
}
方法二：
由我们的图论模型可以得出一个结论：我们只会选一种$n-2a_i>0$的$a_i$和一种$n-2a_i<0$的$a_i$。
证明：
考虑同时选取了$a_j$与$a_k$使得$n-2a_j<0$且$n-2a_k<0$，考虑进行$(n-2a_j)(n-2a_k)$的物品拿出
对于选择$j$有$P_j(n-2a_k)$的贡献，对于选择$k$有$P_k(n-2a_j)$的贡献，我们假设$P_j(n-2a_k)>P_k(n-2a_j)$
那么我们进行无限次之后，假定这个次数为$(n-2a_j)(n-2a_k)$的倍数，这样选择$j$的贡献仍然大于选择$k$的贡献，故选择$j$更好。
大于$0$的情况考虑物品贡献即可。
所以我们可以枚举较小的一个$a_i$和较大的一个$a_j$算出以它们为循环节时的答案，所有的答案取$max$即可，时间复杂度为$O(n^2)$
注意：当$n$为偶数时，$\frac{n}{2}$需要特殊判断。
#include<bits/stdc++.h>
using namespace std;
];
int main(){
int N;
;
cin >> N;
; i <= N ; i++)
cin >> p[i];
; i <= N - >> ; i++)
) + ; j <= N ; j++)
* j - N) + p[j] * (N - * i)) / (- * i + * j) > ans)
ans = (p[i] * ( * j - N) + p[j] * (N - * i)) / (- * i + * j);
) == )
ans = max(ans , p[N >> ]);
cout << ) << ans;
;
}