佬们,想知道为什么这题最后用sort一直过不了#2

P2367 语文成绩

dead000 @ 2023-11-30 09:22:44

#include<bits/stdc++.h>
using namespace std;
int a[5000010],b[5000010];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,p;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1]; 
    }
    while(p--){
        int x,y,z;
        cin>>x>>y>>z;
        b[x]+=z;
        b[y+1]-=z;
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+b[i];
    }
    sort(a+1,a+n);
    cout<<a[1];
}

by suyulong1212 @ 2023-11-30 09:28:10

a+n+1


by xczsxczs @ 2023-11-30 09:29:36

@dead000 得用差分,否则会TLE


by xczsxczs @ 2023-11-30 09:30:09

@dead000 不会的话可以看看题解


by dead000 @ 2023-11-30 09:59:09

@xczsxczs 哥,我这个不就是差分吗


by 沉石鱼惊旋 @ 2023-11-30 11:00:26

@dead000 sort 是左闭右开的,最右边取不到 a+n,要写成 a+n-1


by 沉石鱼惊旋 @ 2023-11-30 11:00:45

不是,a+n+1


by lightme @ 2023-12-12 21:52:35

就是排序这边的问题,已证


by PURE_LOVE @ 2024-02-05 18:06:35

@dead000 哥我那也过不去,想问一下最后你是怎么过的,谢谢佬。


by dead000 @ 2024-02-05 18:47:32

@PURE_LOVE 跟我一样的问题吗,我说sort排序少了个+1


by PURE_LOVE @ 2024-02-05 19:48:08

@dead000 我用的qsort,要不哥你帮我看看吧


#include<bits/stdc++.h>
int cmp(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}
void chafen(int left,int right,int value,int xrr[])
{
    int n = sizeof(xrr) / 4;
    xrr[left-1] += value;
    if (right < n)
    {
        xrr[right ] -= value;
    }
    return;
}
int main()
{
    int n = 0, p = 0;
    scanf("%d%d", &n, &p);
    int* arr = (int*)malloc(n * sizeof(int));
    int* temp = (int*)malloc(n * sizeof(int));
    int* xrr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        if (i == 0)
        {
            xrr[i] = arr[i];
        }
        else
        {
            xrr[i] = arr[i] - arr[i - 1];
        }
    }
    while (p--)
    {
        int left = 0, right = 0, value = 0;
        scanf("%d%d%d", &left, &right, &value);
        chafen(left, right, value,xrr);
    }
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            arr[i] = xrr[i];
        }
        else
        {
            arr[i] = arr[i-1] + xrr[i];
        }
    }
    qsort(arr,n,sizeof(int),cmp);
    if(arr[0]>0)
    {printf("%d", arr[0]);}
    else
    {printf("0");}
}```c

| 下一页