4788. 大數(shù)量

某商場在一天中一共來了?nn?個客人。

10年積累的網(wǎng)站建設、成都網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站制作后付款的網(wǎng)站建設流程，更有太白免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

每個客人進入商場的具體時刻（精確到分鐘）已知。

請你計算并輸出在同一時刻（精確到分鐘）進入商場的大客人數(shù)量。

輸入格式

第一行包含整數(shù)?nn。

接下來?nn?行，每行包含兩個整數(shù)?h,mh,m，表示一個客人在?hh?時?mm?分進入商場。

所有時間都按照時間先后順序給出。

時間采用?2424?小時制。

輸出格式

一個整數(shù)，表示在同一時刻（精確到分鐘）進入商場的大客人數(shù)量。

數(shù)據(jù)范圍

前?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周賽最水的題，這道題也不例外。把小時分鐘換成一個數(shù)，然后用暴力枚舉即可，時間復雜度不高。

具體步驟如下（定義，輸入除外）：

1.把時間轉(zhuǎn)換為分鐘制，就是一個數(shù)t。

2.把這個時間對應的數(shù)組元素計數(shù)， 也就是cnt[t]++，是客人在這個時間來的人數(shù)

3.答案不斷更新，每次更新為之前的答案與這個時間客人來的人數(shù)的大值

4.輸出答案

完整代碼如下（已AC）：

//第84周周賽4788. 大數(shù)量
#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?的正整數(shù)序列?a1,a2,…,ana1,a2,…,an。

如果將該序列從小到大排序，則可以得到另一個長度為?nn?的正整數(shù)序列?b1,b2,…,bnb1,b2,…,bn。

現(xiàn)在，請你回答?mm?個詢問，詢問共分為以下兩種：

• 1 l r，請你計算并輸出?∑i=lrai∑i=lrai。
• 2 l r，請你計算并輸出?∑i=lrbi∑i=lrbi。

輸入格式

第一行包含整數(shù)?nn。

第二行包含?nn?個正整數(shù)?a1,a2,…,ana1,a2,…,an。

第三行包含整數(shù)?mm。

接下來?mm?行，每行包含一個詢問，格式如題面描述。

輸出格式

共?mm?行，每個詢問輸出一行答案。

數(shù)據(jù)范圍

前?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

思路：運用了前綴和算法（技巧）。

前綴和算法就是優(yōu)化時間復雜度的一個算法。把每個元素都變成前一個元素數(shù)加上當前的。

核心代碼如下：

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. 買可樂

某商店目前庫存可樂數(shù)量為?kk?瓶。

可樂的進貨價格如下：

• 整箱：cc?元/箱。每箱有?nn?瓶。
• 單瓶：dd?元/瓶。

請問，為了使得庫存可樂數(shù)量不低于?n×mn×m?瓶，該商店至少需要花費多少元錢來購進可樂。

顯然，當?k≥n×mk≥n×m?時，無需購進可樂。

輸入格式

第一行包含兩個整數(shù)?c,dc,d。

第二行包含兩個整數(shù)?n,mn,m。

第三行包含整數(shù)?kk。

輸出格式

一個整數(shù)，表示最少花費的金額。

數(shù)圍范據(jù)

前?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.能買整箱買整箱，剩下的零頭買單瓶

最后求最小值即可，本題未優(yōu)化。

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

請您點贊，關注加收藏，謝謝您的閱讀！

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：acwing第84場周賽（4788，4789，4890）題解-創(chuàng)新互聯(lián)
鏈接地址：http://chinadenli.net/article36/edopg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站營銷、自適應網(wǎng)站、手機網(wǎng)站建設、App設計、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)