期末预测之安全指数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, sum = 0;
    cin>>n;
    while(n--){
        int s, w;
        cin>>s>>w;
        sum += (s*w);
    }
    int ans = max(0, sum);
    cout<<ans;
    return 0;
}

1
2
3
4
5
6
7
8

n = int(input())
sum = 0
for i in range(0, n):
    s, w = map(int, input().split())
    sum = sum + s * w
ans = max(0, sum)

print(ans)

期末预测之最佳阈值

关键：巧妙的将计数转变为前缀和问题 问题的关键在于如何快速的统计每一个阈值预测正确的个数？ Y 总的方法是采用前缀和的方法来统计个数，如何将分散的数据转变为可以用前缀和的数据呢，就是按照阈值对数据进行排序。这样的效果就是阈值 i 预测正确的个数就是在 i 前的数据的预测结果为 0 的个数加上在 i 后数据预测结果为 1 的个数。 那么我们维护两个前缀和数组 s1 和 s0，s1 [i]表示 i 前（包括 i）的数据中 1 的个数，s0 [i]同理。那么对于数据 i 对应的阈值来说，预测正确的个数就是 s1 [m] - s1 [i - 1] + s0[i - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int>PII;
const int N = 100010;
PII p[N];
int s[2][N];

int main(){
    int m;
    cin>>m;
    for(int i = 1; i <= m; i ++){
        cin>>p[i].x>>p[i].y;
    }
    sort(p + 1, p + m + 1); // 排序，目的是为了方便使用前缀和算法
    
    for(int i = 0; i < 2; i ++){
        for(int j = 1; j <= m; j ++){
            s[i][j] = s[i][j - 1] + (p[j].y == i); //维护前缀和数组
        }
    }
    int res , cnt = -1;
    for(int i = 1; i <= m; i ++){
        int t = s[0][i - 1] + s[1][m] - s[1][i - 1];
        if(t >= cnt) cnt = t, res = p[i].x;
        while(i + 1 <= m && p[i].x == p[i + 1].x) i++; //因为x（阈值）有相同的值，那么计算该阈值的正确预测个数，用的应该是最后出现的一个阈值对应的前缀和
    }
    cout<<res;
    return 0;
}