[已解决]这道题怎么做

张育玮

如图

最佳答案

月排行榜 / 总排行榜

Hello.

2022-8-20 22:54:12

这是总和大于 0 的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
struct node {
    int val, th;
    bool operator < (const node &k) const {
        if (val != k.val) return val < k.val;
        else return th > k.th;
    }
} a[maxn];
int c[maxn];
int n;
int lowbit(int x) { return x & -x; }
void add(int i, int x)
{
    while (i <= n) {
        c[i] += x;
        i += lowbit(i);
    }
}
int que(int i)
{
    int ret = 0;
    while (i > 0) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}
signed main()
{
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i].val);
        a[i].val += a[i - 1].val;
        a[i].th = i;
        if (a[i].val > 0) ans++;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        a[a[i].th].val = i;
    }
    for (int i = 1; i <= n; i++) {
        ans += que(a[i].val - 1);
        add(a[i].val, 1);
    }
    cout << ans;
    return 0;
}

跳转到最佳答案楼层

Hello.

这是总和大于 0 的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
struct node {
    int val, th;
    bool operator < (const node &k) const {
        if (val != k.val) return val < k.val;
        else return th > k.th;
    }
} a[maxn];
int c[maxn];
int n;
int lowbit(int x) { return x & -x; }
void add(int i, int x)
{
    while (i <= n) {
        c[i] += x;
        i += lowbit(i);
    }
}
int que(int i)
{
    int ret = 0;
    while (i > 0) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}
signed main()
{
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i].val);
        a[i].val += a[i - 1].val;
        a[i].th = i;
        if (a[i].val > 0) ans++;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        a[a[i].th].val = i;
    }
    for (int i = 1; i <= n; i++) {
        ans += que(a[i].val - 1);
        add(a[i].val, 1);
    }
    cout << ans;
    return 0;
}

jhq999

#include <stdio.h>
int main()
{
        int i=0,j=0,n=0,k=0,count=0;
        scanf("%d",&n);
        int *a=(int *)malloc(n*sizeof(int));
        for(i=0;i<n;i+=1)scanf("%d",a+i);
        scanf("%d",&k);
        for(i=0;i<n;i+=1)
        {
                int sum=0;
                for(j=i,sum=a[i];j<n&&sum<=5;j+=1,sum+=a[j])
                {

                        count+=1;
                }
        }
        printf("%d",count);
        free(a);
        return 0;
}

傻眼貓咪

Hello. 发表于 2022-8-20 22:54
这是总和大于 0 的代码

你的代码思路很厉害。

我比较好奇，为什么要用：

#include <iostream>
#define int long long

signed main(void) {
        return 0;
}

而不直接用：

#include <iostream>

int main(void) {
        return 0;
}

以上两种不是都一样吗？

Hello.

傻眼貓咪 发表于 2022-8-21 11:20
你的代码思路很厉害。

我比较好奇，为什么要用：

防止出现大量运算爆 int
应试技巧
你的当然更好

柿子饼同学

Hello. 发表于 2022-8-20 22:54
这是总和大于 0 的代码

树状数组?

Hello.

柿子饼同学 发表于 2022-8-21 13:20
树状数组?