NK16

C 小石的海岛之旅

链接：https://ac.nowcoder.com/acm/contest/949/C
来源：牛客网

暑假到了，小石和小雨到海岛上玩。
从水平方向看海岛可以看成

nnn个小块，每一个小块都有一个高度hih_ihi​， 水位一开始为 000，随着水位的上升，海岛分成了若干块。 现在有 mmm 个询问，求当水位为aia_iai​ 时，海岛会分成多少块。

输入描述:

第一行输入两个正整数 $hih_ihi​，表示每一块的高度。第三行输入 mmm个整数 aia_iai​，表示每一个询问，保证输入的 aia_iai​ 单调递增。$

输出描述:

共

示例1

输入

复制

7 3
1 2 3 1 2 1 3
1 2 3

输出

复制

3
2
0

说明

当水位高度为 1 时，岛屿被分成 3 块，2 3；2；3

当水位高度为 2 时，岛屿被分成 2 块：3；3 。

当水位高度为 3 时，岛屿全部被淹没，剩余 0 块 。
思路：只有当左边的高度比水位低，右边的高度比水位高的时候才会被分割

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1E3+7;
    int arr[N];
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&arr[i]);
        }
        int y;
        for(int j=1;j<=m;j++){
            scanf("%d",&y);
            int x=0;
            for(int i=1;i<=n;i++){
                if(arr[i]>y&&arr[i-1]<=y){
                    x++;
                }
            }
            printf("%d
",x);
        }
        return 0;
    }

D 小杨买水果

链接：https://ac.nowcoder.com/acm/contest/949/D
来源：牛客网

水果店里有

aia_iai​，最终的满意度为他买到的水果的喜欢程度之和。 如果和为正（不管是正多少，只要大于 000 即可），他就满意了。

小阳想知道在他满意的条件下最多能买多少个水果。

输入描述:

第一行输入一个正整数 n，表示水果总数。

第二行输入 n 个整数  $aia_iai​，表示小阳对每个水果的喜爱程度。$

输出描述:

一行一个整数表示结果。（如果 1 个水果都买不了，请输出 0）

示例1

输入

复制

5
0 0 -7 -6 1

输出

复制

1
题解：构造一个前缀和，并对前缀和进行排序，从小到大排序，前缀和相同的，下标大的在前边，我要让起始点参与排序，因为有可能某一个前缀本身就是最优解，（不太理解）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2E6+7;
int  arr[N];
struct stu{
    int  a;
    int  b;
    bool friend operator<(const stu &x,const stu &y){
        if(x.a!=y.a)return x.a<y.a;
        return x.b>y.b;
    }
}sum[N];
int main(){
    int n;
    cin>>n;
    sum[0].a=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);.
        sum[i].a=sum[i-1].a+arr[i];
        sum[i].b=i;
    }
    sort(sum,sum+1+n);
    int min1=n+1;
    int ans=0;
    for(int i=0;i<=n;i++){
        ans=max(ans,sum[i].b-min1);
        min1=min(sum[i].b,min1);
    }
    cout<<ans<<endl;
    return 0;
}

第二种解法：二分！！（还是不理解）

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 1e6*2+10;
ll a[MAX];
ll x,w;
int ans;

int main(){
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n;i++){
        scanf("%lld",&x);
        w+=x;
        a[i]=min(a[i-1],w);
        
        if(w>0){//总和大于0，特判
            ans=max(ans,i);//不需要减1
            continue;
        }
        
        int l=1,r=i;
        while(l<=r){//二分找左边最小值
            int mid=(l+r)>>1;
            if(a[mid]<w) r=mid-1;
            else l=mid+1;
        }
        ans=max(ans,i-r-1);//需要减1，自己推一下，不好解释~~（
        //大体就是找到右边小于0的那一块，多了一个负值，把多的那个值去掉，右边就是大于0的，
        //当然那个负值在右边那一块的最左边）
    
    }
    printf("%lld
",ans);
    return 0;
}