[已解决]这道题怎么做

张育玮

如图

最佳答案

月排行榜 / 总排行榜

Hello.

2022-8-20 22:54:12

这是总和大于 0 的代码

1. #include <bits/stdc++.h>
   
2. #define int long long
   
3. using namespace std;
   
4. const int maxn = 1e6 + 5;
   
5. struct node {
   
6.     int val, th;
   
7.     bool operator < (const node &k) const {
   
8.         if (val != k.val) return val < k.val;
   
9.         else return th > k.th;
   
10.     }
    
11. } a[maxn];
    
12. int c[maxn];
    
13. int n;
    
14. int lowbit(int x) { return x & -x; }
    
15. void add(int i, int x)
    
16. {
    
17.     while (i <= n) {
    
18.         c[i] += x;
    
19.         i += lowbit(i);
    
20.     }
    
21. }
    
22. int que(int i)
    
23. {
    
24.     int ret = 0;
    
25.     while (i > 0) {
    
26.         ret += c[i];
    
27.         i -= lowbit(i);
    
28.     }
    
29.     return ret;
    
30. }
    
31. signed main()
    
32. {
    
33.     cin >> n;
    
34.     int ans = 0;
    
35.     for (int i = 1; i <= n; i++) {
    
36.         scanf("%lld", &a[i].val);
    
37.         a[i].val += a[i - 1].val;
    
38.         a[i].th = i;
    
39.         if (a[i].val > 0) ans++;
    
40.     }
    
41.     sort(a + 1, a + 1 + n);
    
42.     for (int i = 1; i <= n; i++) {
    
43.         a[a[i].th].val = i;
    
44.     }
    
45.     for (int i = 1; i <= n; i++) {
    
46.         ans += que(a[i].val - 1);
    
47.         add(a[i].val, 1);
    
48.     }
    
49.     cout << ans;
    
50.     return 0;
    
51. }

复制代码

跳转到最佳答案楼层

Hello.

这是总和大于 0 的代码

1. #include <bits/stdc++.h>
   
2. #define int long long
   
3. using namespace std;
   
4. const int maxn = 1e6 + 5;
   
5. struct node {
   
6.     int val, th;
   
7.     bool operator < (const node &k) const {
   
8.         if (val != k.val) return val < k.val;
   
9.         else return th > k.th;
   
10.     }
    
11. } a[maxn];
    
12. int c[maxn];
    
13. int n;
    
14. int lowbit(int x) { return x & -x; }
    
15. void add(int i, int x)
    
16. {
    
17.     while (i <= n) {
    
18.         c[i] += x;
    
19.         i += lowbit(i);
    
20.     }
    
21. }
    
22. int que(int i)
    
23. {
    
24.     int ret = 0;
    
25.     while (i > 0) {
    
26.         ret += c[i];
    
27.         i -= lowbit(i);
    
28.     }
    
29.     return ret;
    
30. }
    
31. signed main()
    
32. {
    
33.     cin >> n;
    
34.     int ans = 0;
    
35.     for (int i = 1; i <= n; i++) {
    
36.         scanf("%lld", &a[i].val);
    
37.         a[i].val += a[i - 1].val;
    
38.         a[i].th = i;
    
39.         if (a[i].val > 0) ans++;
    
40.     }
    
41.     sort(a + 1, a + 1 + n);
    
42.     for (int i = 1; i <= n; i++) {
    
43.         a[a[i].th].val = i;
    
44.     }
    
45.     for (int i = 1; i <= n; i++) {
    
46.         ans += que(a[i].val - 1);
    
47.         add(a[i].val, 1);
    
48.     }
    
49.     cout << ans;
    
50.     return 0;
    
51. }

复制代码

jhq999

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.         int i=0,j=0,n=0,k=0,count=0;
   
5.         scanf("%d",&n);
   
6.         int *a=(int *)malloc(n*sizeof(int));
   
7.         for(i=0;i<n;i+=1)scanf("%d",a+i);
   
8.         scanf("%d",&k);
   
9.         for(i=0;i<n;i+=1)
   
10.         {
    
11.                 int sum=0;
    
12.                 for(j=i,sum=a[i];j<n&&sum<=5;j+=1,sum+=a[j])
    
13.                 {
    
14. 
    
15.                         count+=1;
    
16.                 }
    
17.         }
    
18.         printf("%d",count);
    
19.         free(a);
    
20.         return 0;
    
21. }

复制代码

傻眼貓咪

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

你的代码思路很厉害。

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

1. #include <iostream>
   
2. #define int long long
   
3. 
   
4. signed main(void) {
   
5.         return 0;
   
6. }

复制代码

而不直接用：

1. #include <iostream>
   
2. 
   
3. int main(void) {
   
4.         return 0;
   
5. }

复制代码

以上两种不是都一样吗？

Hello.

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

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

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

柿子饼同学

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

树状数组?

Hello.

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