PAT 1044 Shopping in Mars 利用二分查找优化时间复杂度

快来打我* 2023-02-27 13:53 12阅读 0赞

# 1044 Shopping in Mars (25分) #

需要找到一段数列，其和最接近m。  
需要求某一段的和就使用s\[\]数组存储前n项和，s\[j\]-s\[i-1\]==m则表明i~j之前和为m。  
注意下标从1开始，较为方便。

## O(n^2)暴力超时做法 ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100010;
    int n, m, tmp, s[maxn];
    int minn = INT_MAX;
    vector<pair<int, int>> v;
    
    int main() { 
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt", "r", stdin);
    #endif
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; ++i) { 
            scanf("%d",&tmp);
            s[i] = s[i - 1] + tmp;
        }
        for (int i = 1; i <= n; ++i) { 
            for (int j = i; j <= n; ++j) { 
                if (s[j] - s[i - 1] >= m) { 
                    if (s[j] - s[i - 1] - m < minn) { 
                        minn=s[j] - s[i - 1] - m;
                        v.clear();
                        v.push_back({ i, j});
                    } else if (s[j] - s[i - 1] - m == minn) { 
                        v.push_back({ i, j});
                    }
                    break;//剪枝只能多过一个点
                }
            }
        }
        for(int i=0;i<v.size();i++) { 
            printf("%d-%d\n",v[i].first,v[i].second);
        }
        return 0;
    }

## 二分查找优化做法 ##

lower\_bound二分查找可以在有序数组找到第一个满足大于等于某数的位置  
题目所求的就是满足s\[j\]-s\[i-1\]>=m且s\[j\]-s\[i-1\]最小的i~j，即对每一个i求满足s\[j\]>=m+s\[i-1\]的最小的j值。前n项和显然有序，可以用二分查找降低复杂度。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100010;
    int n, m, tmp, s[maxn];
    int minn = INT_MAX;
    vector<pair<int, int>> v;
    
    int main() { 
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt", "r", stdin);
    #endif
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; ++i) { 
            scanf("%d",&tmp);
            s[i] = s[i - 1] + tmp;
        }
        for (int i = 1; i <= n; ++i) { 
            int low=lower_bound(s+i,s+n,s[i-1]+m)-s;//low为第一个满足s[low]大于等于s[i-1]+m的下标
            if(s[low]-s[i-1]>=m){ 
                if(s[low]-s[i-1]<minn){ 
                    minn=s[low]-s[i-1];
                    v.clear();
                    v.push_back({ i,low});
                }
                else if(s[low]-s[i-1]==minn){ 
                    v.push_back({ i,low});
                }
            }
        }
        for(int i=0;i<v.size();i++) { 
            printf("%d-%d\n",v[i].first,v[i].second);
        }
        return 0;
    }

## 二分查找stl总结 ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    { 
        int a[100]= { 4,10,11,30,69,70,96,100};
        int b=binary_search(a,a+9,4);//查找成功，返回1
        cout<<"在数组中查找元素4，结果为："<<b<<endl;
        int c=binary_search(a,a+9,40);//查找失败，返回0
        cout<<"在数组中查找元素40，结果为："<<c<<endl;
        int d=lower_bound(a,a+9,10)-a;
        cout<<"在数组中查找第一个大于等于10的元素位置，结果为："<<d<<endl;
        int e=lower_bound(a,a+9,101)-a;
        cout<<"在数组中查找第一个大于等于101的元素位置，结果为："<<e<<endl;
        int f=upper_bound(a,a+9,10)-a;
        cout<<"在数组中查找第一个大于10的元素位置，结果为："<<f<<endl;
        int g=upper_bound(a,a+9,101)-a;
        cout<<"在数组中查找第一个大于101的元素位置，结果为："<<g<<endl;
    }

binary\_search找等于，找到了返回1，找不到了返回0  
lower\_bound找刚好>=，找到了返回指针，找不到返回a+n（就是第二个参数）  
upper\_bound找刚好>，找到了返回指针，找不到返回a+n（就是第二个参数）