a. 期末预测之安全指数
题意
给定 n 个 \(w_{i}\) 和 \(score_{i}\)，求出二者乘积和，输出这个数和0的最大值
数据范围
\(2\leq n\leq 10^{5}\)
\(-10\leq w_{i}\leq 10\)
\(0\leq score_{i}\leq 100\)
题解
- 按照题意做即可
Code
cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i ++)
int main ()
{
int n; cin>>n;
int res = 0;
rep(i, 0, n)
{
int a, b; cin>>a>>b;
res += a * b;
}
cout <<max(res,0)<<endl;
}
b. 期末预测之最佳阈值
题意
给定 \(m\) 组成绩 \(y_{i}\) 和其预测值 \(predict_{i}\)，如果将其中一个值定为阈值 \(\theta\)，
\[\operatorname{predict}_{\theta}(y)=\left\{\begin{array}{l}0(y<\theta) \\ 1(y \geq \theta)\end{array}\right. \]求出使得预测结果正确数量最大的阈值，如果存在多个为阈值最大的
数据范围
\(2\leq m\leq 10^{5}\)
题解
- 数据范围不能 \(O(n^{2})\)，通过前缀和能够达到 \(O(n)\)
- 分别统计每个 0 和 1 的前缀和
- 将数据排序后从小到大遍历更新即可
- 对于相同的只算第一个即可，后面的 0 的前缀和会多计入，且应该属于 \(\geq\)
Code
cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(register int i = a; i < n; i ++)
#define fi first
#define se second
const int N = 1e5 + 10;
typedef pair<int,int> pii;
int s[2][N];
pii a[N];
int main()
{
int m; cin>>m;
rep(i, 1, m + 1) cin>>a[i].fi>>a[i].se;
sort(a + 1, a + m + 1);
rep(i, 0, 2)
{
rep(j, 1, m+1)
{
s[i][j] = s[i][j - 1] + (a[j].se == i);
}
}
pii ans = {0, -1};
rep(i, 1, m + 1)
{
pii now = {a[i].fi, s[0][i - 1] + s[1][m] - s[1][i - 1]};
if(now.se >= ans.se) ans = now;
while(i + 1 <= m && a[i + 1].fi == a[i].fi) i ++;
}
cout<<ans.fi;
}
c. 命令行选项
题意
数据范围
题解
Code
cpp
d. 无线网络
题意
数据范围
题解
Code
cpp
e. 出现次数最多的数
题意
数据范围
题解
Code
cpp