建站
咨詢
售后
建站咨詢
新聞中心
某商場在一天中一共來了?nn?個客人。
每個客人進入商場的具體時刻（精確到分鐘）已知。
請你計算并輸出在同一時刻（精確到分鐘）進入商場的大客人數(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ù)，然后用暴力枚舉即可，時間復(fù)雜度不高。
具體步驟如下（定義，輸入除外）：
1.把時間轉(zhuǎn)換為分鐘制，就是一個數(shù)t。
2.把這個時間對應(yīng)的數(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]);//在同一個點上如果重復(fù)就加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)化時間復(fù)雜度的一個算法。把每個元素都變成前一個元素數(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;
} 請您點贊，關(guān)注加收藏，謝謝您的閱讀！
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
標題名稱：acwing第84場周賽（4788，4789，4890）題解-創(chuàng)新互聯(lián)
分享路徑：http://fisionsoft.com.cn/article/edopg.html
