大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

acwing第84场周赛(4788,4789,4890)题解-创新互联

4788. 大数量

某商场在一天中一共来了 nn 个客人。

10年积累的网站建设、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站制作后付款的网站建设流程,更有太白免费网站建设让你可以放心的选择与我们合作。

每个客人进入商场的具体时刻(精确到分钟)已知。

请你计算并输出在同一时刻(精确到分钟)进入商场的大客人数量。

输入格式

第一行包含整数 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≤gif.latex?10%5E%7B5%7D,1≤ai≤gif.latex?10%5E%7B9%7D,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://dzwzjz.com/article/edopg.html
在线咨询
服务热线
服务热线:028-86922220
TOP