ccpc|The 2021 CCPC Weihai Onsite E. CHASE! 算法|c++

Setsuna likes staying at home. No matter what happens at school, she has little interest and only wants to go home to play games. One day when she was back, she opened a rhythm game and found that her favorite event was helding.
For each round in this event, a player has to play two different songs which are randomly chosen by system. There are totally nn songs in the system, and Setsuna is able to gain a score of aiai if she plays the ii-th song. The score of a round is the sum of scores of the two songs.
Initially the system presents two different songs which are randomly selected with equal probability. If the player is unsatisfied with the result, he can ask the system to reselect (of course randomly). But there are only kk opportunities of reselecting in total.
Setsuna had many questions. Firstly, she wanted to know her expected score under optimal decision. Secondly, she assumpted QQ cases, each of which was as the form of "the system selected the xx-th song and the yy-th song currently, and there were cc chances of reselecting left", and you need to answer whether she should accept the result, or decide to reselect, or both are OK if the difference of expected scores of these two choices under optimal decision is less or equal than 10?410?4.
Input
The first line containts three integers n,k,Qn,k,Q. (2≤n≤105, 1≤Q≤105, 0≤k≤1002≤n≤105, 1≤Q≤105, 0≤k≤100)
The second line contains nn integers a1,?,ana1,?,an. (0≤ai≤1060≤ai≤106)
Next QQ lines each contains three integers x,y,cx,y,c. (1≤x Output
The first line contains a real number, representing the maximum expected score. The absolute difference between your answer and the standard answer should be within 10?410?4.
For next QQ lines, if she should accept the result in the ii-th case, output "accept"; if she should reselect, output "reselect"; if both are OK, output "both".
Example
input
Copy

3 2 1 30 40 50 1 2 1

output
Copy

85.555555556 reselect

ccpc|The 2021 CCPC Weihai Onsite E. CHASE!

文章图片

#include using namespace std; #define sc(x) scanf("%d",&x) #define sl(x) scanf("%lld",&x) #define ll long long #define pb push_back typedef pairPII; const ll INF=1e18+5; const int mod=1e9+7; const int Max=1e6+5; ll n,k,q; ll a[Max]; double f[Max]; ll num=0; ll sum[Max]; ll solve(double x){ ll ret=0; for (int l = 1, r = n; l <= n; l ++){ if(r <= l) r = l + 1; while(1){ if(r == l + 1 || a[r - 1] + a[l] < x) break; r --; } if(a[r] + a[l] >= x){ num += n - r + 1; ret += sum[n] - sum[r - 1]; ret += (n - r + 1) * a[l]; } } return ret; } ll C2(ll n){ return n * (n - 1) / 2; } ll b[Max]; int main(){ sl(n); sl(k); sl(q); ll ans=0; for(int i=1; i<=n; i++) sl(a[i]),ans+=1LL * a[i] * (n-1),b[i]=a[i]; f[0]=2.0 * ans / (n*(n-1)); sort(a+1,a+1+n); for(int i=1; i<=n; i++) sum[i]=sum[i-1]+a[i]; for(int i=1; i<=k; i++){ num=0; ll ret=solve(f[i-1]); f[i]=2.0 * (f[i-1]*((n*(n-1)/2-num))+ret) / (n*(n-1)); } printf("%.9lf\n",f[k]); while(q--){ ll x, y, c; scanf("%lld%lld%lld", &x, &y, &c); if (c == 0) printf("accept\n"); else { c --; double cursum = b[x] + b[y]; if(fabs(f[c] - cursum) < 1e-4) puts("both"); else if(f[c] < cursum) puts("accept"); else puts("reselect"); } } }

掉坑点：
1.一直以为题意中的left是左边，但是居然是留下，焯，卡一小时
2.运用双指针时，需要先排序，但是忘记保留原数组了！！！！
3.双指针求每个点贡献错误！！！
【ccpc|The 2021 CCPC Weihai Onsite E. CHASE!】4.long double%Lf输出，不然报错！！！