acwing第84场周赛（4788，4789，4890）题解-创新互联
某商场在一天中一共来了 nn 个客人。
每个客人进入商场的具体时刻（精确到分钟）已知。
请你计算并输出在同一时刻（精确到分钟）进入商场的大客人数量。
输入格式
第一行包含整数 nn。
接下来 nn 行，每行包含两个整数 h,mh,m，表示一个客人在 hh 时 mm 分进入商场。
所有时间都按照时间先后顺序给出。
时间采用 2424 小时制。
输出格式
一个整数，表示在同一时刻（精确到分钟）进入商场的大客人数量。
数据范围
前 55 个测试点满足 1≤n≤101≤n≤10。
所有测试点满足 1≤n≤1051≤n≤105，0≤hi≤230≤hi≤23，0≤mi≤590≤mi≤59。
输入样例1：
4
8 0
8 10
8 10
8 45输出样例1：
2输入样例2：
3
0 12
10 11
22 22输出样例2：
1思路：
第一题向来都是acwing周赛最水的题，这道题也不例外。把小时分钟换成一个数，然后用暴力枚举即可，时间复杂度不高。
具体步骤如下（定义，输入除外）：
1.把时间转换为分钟制，就是一个数t。
2.把这个时间对应的数组元素计数， 也就是cnt[t]++，是客人在这个时间来的人数
3.答案不断更新，每次更新为之前的答案与这个时间客人来的人数的大值
4.输出答案
完整代码如下（已AC）：
//第84周周赛4788. 大数量
#includeusing namespace std;
int cnt[100001];
int n;
int main()
{
scanf("%d", &n);
int h, m;
int ans = 0;
for(int i = 1; i<= n; i++)
{
scanf("%d%d", &h, &m);
int t = 60 * h + m;
cnt[t]++;
ans = max(ans, cnt[t]);//在同一个点上如果重复就加1，这样就直接算出大值
}
cout<< ans<< endl;
return 0;
} 看完第一题，接下来我们再来看第二题。先看题目：
4789. 前缀和序列给定一个长度为 nn 的正整数序列 a1,a2,…,ana1,a2,…,an。
如果将该序列从小到大排序，则可以得到另一个长度为 nn 的正整数序列 b1,b2,…,bnb1,b2,…,bn。
现在，请你回答 mm 个询问，询问共分为以下两种：
1 l r，请你计算并输出 ∑i=lrai∑i=lrai。2 l r，请你计算并输出 ∑i=lrbi∑i=lrbi。
输入格式
第一行包含整数 nn。
第二行包含 nn 个正整数 a1,a2,…,ana1,a2,…,an。
第三行包含整数 mm。
接下来 mm 行，每行包含一个询问，格式如题面描述。
输出格式
共 mm 行，每个询问输出一行答案。
数据范围
前 3 个测试点满足 1≤n,m≤10
所有测试点满足 1≤n,m≤
，1≤ai≤，1≤l≤r≤n。
输入样例1：
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6输出样例1：
24
9
28输入样例2：
4
5 5 2 3
10
1 2 4
2 1 4
1 1 1
2 1 4
2 1 2
1 1 1
1 3 3
1 1 3
1 4 4
1 2 2输出样例2：
10
15
5
15
5
5
2
12
3
5输入样例3：
4
2 2 3 6
9
2 2 3
1 1 3
2 2 3
2 2 3
2 2 2
1 1 3
1 1 3
2 1 4
1 1 2输出样例3：
5
7
5
5
2
7
7
13
4思路：运用了前缀和算法（技巧）。
前缀和算法就是优化时间复杂度的一个算法。把每个元素都变成前一个元素数加上当前的。
核心代码如下：
sort(b + 1, b + 1 + n);
for(long long i = 2; i<= n; i++)
{
a[i] = a[i - 1] + a[i];
}
for(long long i = 2; i<= n; i++)
{
b[i] = b[i - 1] + b[i];
}完整ac代码如下：
//第84周周赛4789. 前缀和序列
#includeusing namespace std;
long long a[100001], b[100001];
long long n, m;
int main()
{
scanf("%lld", &n);
for(long long i = 1; i<= n; i++)
{
scanf("%lld", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
for(long long i = 2; i<= n; i++)
{
a[i] = a[i - 1] + a[i];
}
for(long long i = 2; i<= n; i++)
{
b[i] = b[i - 1] + b[i];
}
scanf("%lld", &m);
for(long long i = 1; i<= m; i++)
{
long long f;
scanf("%lld", &f);
if(f == 1)
{
long long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", a[r] - a[l - 1]);
}
else
{
long long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", b[r] - b[l - 1]);
}
}
return 0;
} 再来看最后一道题。
4790. 买可乐某商店目前库存可乐数量为 kk 瓶。
可乐的进货价格如下：
- 整箱：cc 元/箱。每箱有 nn 瓶。
- 单瓶：dd 元/瓶。
请问，为了使得库存可乐数量不低于 n×mn×m 瓶，该商店至少需要花费多少元钱来购进可乐。
显然，当 k≥n×mk≥n×m 时，无需购进可乐。
输入格式
第一行包含两个整数 c,dc,d。
第二行包含两个整数 n,mn,m。
第三行包含整数 kk。
输出格式
一个整数，表示最少花费的金额。
数围范据
前 44 个测试点满足 1≤c,d,n,m,k≤101≤c,d,n,m,k≤10。
所有测试点满足 1≤c,d,n,m,k≤1001≤c,d,n,m,k≤100。
输入样例1：
1 10
7 2
1输出样例1：
2输入样例2：
2 2
2 1
2输出样例2：
0思路：
一共分为三种情况：
1.全买整箱的
2.全买单瓶的
3.能买整箱买整箱，剩下的零头买单瓶
最后求最小值即可，本题未优化。
完整ac代码如下：
//第84周周赛4790. 买可乐
#includeusing namespace std;
int c, d, m, n, k, xuyao, ans1, ans2, ans3, answer;
int main()
{
cin >>c >>d >>n >>m >>k;
if(k >= m * n)
{
cout<< 0<< endl;
return 0;
}
xuyao = n * m - k;
ans1 = xuyao / n * c + xuyao % n * d;
ans2 = xuyao / n * c + c;
ans3 = xuyao * d;
answer = min(ans3, min(ans1, ans2));
cout<< answer<< endl;
return 0;
} 请您点赞，关注加收藏，谢谢您的阅读！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：acwing第84场周赛（4788，4789，4890）题解-创新互联
当前地址：http://scjbc.cn/article/edopg.html
