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;
}

看完第一题，接下来我们再来看第二题。先看题目：

给定一个长度为 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;
}

再来看最后一道题。

某商店目前库存可乐数量为 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元起，快前往官网查看详情吧