蓝桥杯2024年第十五届省赛真题-拔河

审题可能会遇到的问题：认为所有人都必须参与拔河，但其实不用，只要符合l1<=r1

正解思路：前缀和+枚举+二分。枚举左区间，利用二分来选择右区间。时间复杂度O(N^2*logn)能满足题目要求。先利用前缀和求出任意两点间的区间和，然后存入multiset中。然后枚举左区间的右端点，期间先删除以这个右端点为左端点的右区间，然后再枚举左区间，在所有右区间中，找到和左区间值最近的右区间（一个大于它一个小于它），然后计算差值，记录答案。

• 使用前缀和能化简求任意区间和的过程，不用前缀和复杂度为O(n^3)超时。
• 用lower_bound(s.begin(),s.end(),k)速度会比s.lower_bound(k) 慢非常多，使用会超时，原因见文末。
• 这道题输入较多，需要取消输入输出同步流，否则会超时

#include
using namespace std;
#define int long long
#define endl '\n'
#define pp ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N = 1e3+10;

//不去重的排序集合
multiset<int>s;

int a[N];

void solve(){
    //这道题数据量比较多，如果不取消同步流会超时
    pp;
    int n;cin>>n;
    //计算前缀和，方便计算任意区间之和
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    
    //计算区间之和
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            //j==i时，前缀和的差分是原数列
            //j!=i时，是[i,j]之间的区间和
            s.insert(a[j]-a[i-1]);
        
    
    int res = INT_MAX;
    //i是左区间的右端点,注：左区间的右端点不能等于n，因为l2!=r1
    for(int i=1;i<n;i++){
        /*
         删除以i为左端点的所有区间，因为接下来选择右区间用不到，右区间是从i+1开始选择
         并且在i往后拓展时，如果保留之前的以i为左端点的右区间之和，会干扰正确答案
         剩下的s就是所有满足以i为左区间右端点的右区间。
         */
        for(int j=i;j<=n;j++){
            auto add = a[j]-a[i-1];
            s.erase(s.find(add));
        }
        
        //枚举左区间，选择正确的右区间，计算力量值之和差距最小
        for(int j=1;j<=i;j++){
            //左区间之和
            auto k = a[i]-a[j-1];
            //寻找与左区间值最近的右区间
            /**
             lower_bound(s.begin(), s.end(), k)比s.lower_bound(k)慢很多
             */
            auto p = s.lower_bound(k);
            //大于等于k最近的右区间
            if(p!=s.end())res = min(res,abs(*p-k));
            //小于k最近的右区间
            if(p!=s.begin()){
                p--;
                res = min(res,abs(*p-k));
            }
        }
    }
    cout<<res<<endl;
}

signed main(){
    int T=1;
    while(T--)solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

用lower_bound(s.begin(),s.end(),k)速度会比s.lower_bound(k) 慢非常多的原因：

这是因为 lower_bound() 函数是通用的，适用于各种容器类型，而 s.lower_bound(k) 是特定于某个具体容器类型（比如set 或 map）的成员函数。在调用 lower_bound() 时，编译器必须解析和调用一个通用的函数模板，而s.lower_bound(k) 可以直接在编译时确定具体容器类型，并且可以根据该类型进行一些优化。这种差异可能会导致通用的 lower_bound()操作稍微慢一些，因为它需要更多的模板解析和额外的参数推断。但通常情况下，这种差异不会非常显著，除非你在非常大的数据集上运行，并且对性能有极高的要求。