蓝桥杯 无影之谜

原题目链接

问题描述

在 “无影之谜” 解密大赛中，有N位选手，每位选手有一个影响力值S[i]。选手j会投票给选手i，当且仅当选手j的影响力值大于或等于他们之间（不包括选手i和j）其他选手的影响力值的总和。

输入格式

• 第一行包含一个整数N，表示选手的数量。
• 第二行包含N个空格分隔的整数S[1], S[2], ..., S[N]，表示每个选手的影响力值。

输出格式

• 输出一行包含N个空格分隔的整数，表示每个选手得到的投票数。

样例输入

4 4 3 2 1

样例输出

1 2 3 2

这段代码实现了一个优化的算法，用来解决题目中选手投票问题。我们来逐步分析其思路，并与解题过程对照。

c++代码

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;ll N,s,e,temp;ll S[100006],prefix_sum[100006],answer[100006];// 快速求区间和（返回值为ll，避免溢出）llget_interval_sum(inti,intj){if(i<=0||j<=0||i>N||j>N||i>j)return0;returnprefix_sum[j]-prefix_sum[i-1];}// 快速区间加一（差分思想）voidquick_add_one(inti,intj){if(i<=0||j<=0||i>N||j>N||i>j)return;answer[i]++;if(j+1<=N)answer[j+1]--;}intmain(){cin>>N;fill(prefix_sum+1,prefix_sum+N+1,0);fill(answer+1,answer+N+1,0);for(inti=1;i<=N;i++){cin>>S[i];prefix_sum[i]=prefix_sum[i-1]+S[i];}for(inti=1;i<=N;i++){s=1,e=i-1,temp=-1;while(s<=e){intmid=(s+e)/2;if(get_interval_sum(mid+1,i-1)<=S[i]){temp=mid;e=mid-1;}elses=mid+1;}if(temp!=-1)quick_add_one(temp,i-1);s=i+1,e=N,temp=-1;while(s<=e){intmid=(s+e)/2;if(get_interval_sum(i+1,mid-1)<=S[i]){temp=mid;s=mid+1;}elsee=mid-1;}if(temp!=-1)quick_add_one(i+1,temp);}// 计算差分前缀和，得到最终结果for(inti=1;i<=N;i++){answer[i]+=answer[i-1];cout<<answer[i]<<(i==N?"\n":" ");}return0;}//by wqs

思路和步骤分析

1. 前缀和计算

在这个算法中，首先我们使用前缀和数组来高效计算选手之间的影响力值总和。这样对于任意区间[i, j]，我们都可以在O(1)的时间内通过prefix_sum[j] - prefix_sum[i-1]来获得该区间的影响力值和。

llget_interval_sum(inti,intj){if(i<=0||j<=0||i>N||j>N||i>j)return0;returnprefix_sum[j]-prefix_sum[i-1];}

2. 快速区间更新（差分思想）

为了高效地记录每个选手的投票数，我们使用了差分数组answer[]来进行快速更新。对于每一个选手，假设我们找到了满足投票条件的区间，我们可以将该区间的起始位置i处加1，并且在该区间的结束位置j+1处减1。然后，通过累加差分数组，最终得到每个选手的投票数。

voidquick_add_one(inti,intj){if(i<=0||j<=0||i>N||j>N||i>j)return;answer[i]++;if(j+1<=N)answer[j+1]--;}

3. 二分查找优化

接下来，我们使用二分查找来寻找每个选手i在左侧和右侧可以影响的范围。我们要找的条件是，选手j会投票给选手i，当且仅当S[j] >= sum(S[i+1]...S[j-1])。这里的sum(S[i+1]...S[j-1])就是我们通过前缀和数组求得的区间和。

• 左侧范围：我们需要找到选手i左边的选手j，使得从j到i-1之间的总影响力不超过S[i]。我们通过二分查找确定这个范围。
• 右侧范围：同样，我们需要找到选手i右边的选手j，使得从i+1到j-1之间的总影响力不超过S[i]。我们也通过二分查找确定这个范围。

s=1,e=i-1,temp=-1;while(s<=e){intmid=(s+e)/2;if(get_interval_sum(mid+1,i-1)<=S[i]){temp=mid;e=mid-1;}elses=mid+1;}if(temp!=-1)quick_add_one(temp,i-1);s=i+1,e=N,temp=-1;while(s<=e){intmid=(s+e)/2;if(get_interval_sum(i+1,mid-1)<=S[i]){temp=mid;s=mid+1;}elsee=mid-1;}if(temp!=-1)quick_add_one(i+1,temp);

4. 最终结果计算

通过上述步骤，所有满足条件的投票已经通过差分数组answer[]记录下来。最后，我们只需计算前缀和，得到每个选手的投票数。

for(inti=1;i<=N;i++){answer[i]+=answer[i-1];cout<<answer[i]<<(i==N?"\n":" ");}

5. 整体流程

1. 读入数据并初始化前缀和和差分数组。
2. 对每个选手，使用二分查找计算其能影响的区间并更新差分数组。
3. 使用前缀和计算出每个选手的最终投票数并输出结果。

时间复杂度分析

• 前缀和的计算：O(N)，直接遍历一次数组。
• 二分查找：对于每个选手，我们分别进行两次二分查找，每次查找的时间复杂度为O(log N)。所以，总的时间复杂度是O(N log N)。
• 差分数组更新和最终求和：通过差分数组，我们在O(N)时间内完成投票数的更新和计算。

所以，整体时间复杂度为O(N log N)，适合在N较大的情况下使用。

总结

这段代码巧妙地结合了前缀和和差分数组技术，并使用二分查找来优化区间和的计算。这样既能保证算法的正确性，又能够高效地解决大规模数据的处理问题。