f579 - 1. 購物車

🔗 前往 ZeroJudge 原題

題目描述

題目要求統計在 n 位顧客的購物紀錄中，有多少位顧客最終同時購買了商品 a 和商品 b。購物紀錄由一系列整數表示，正數表示放入商品，負數表示取出商品，0 表示紀錄結束。

解題思路

這題可以使用貪心策略和模擬的方法來解決。對於每一位顧客的購物紀錄，我們維護兩個計數器 aa 和 bb，分別記錄商品 a 和商品 b 在購物車中的數量。遍歷購物紀錄，如果遇到商品 a，則 aa 加一；如果遇到商品 b，則 bb 加一；如果遇到取出商品 a，則 aa 減一；如果遇到取出商品 b，則 bb 減一。當遇到紀錄結束符 0 時，判斷 aa 和 bb 是否都大於 0，如果是，則表示該顧客同時購買了商品 a 和商品 b，計數器 ans 加一。

複雜度分析

• 時間複雜度: O(n * m)，其中 n 是顧客數量，m 是每位顧客購物紀錄的長度。最壞情況下，每位顧客的購物紀錄長度相同，因此時間複雜度可以簡化為 O(n * m)。
• 空間複雜度: O(1)，因為我們只使用了幾個整數變數來記錄計數器和結果，空間使用量不隨輸入規模的增加而增加。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int a,b,n,k,aa=0,bb=0,ans=0;
	cin >> a >> b >> n;
	while(n){
		cin >> k;
		if(!k){
			--n;
			if(aa>0&&bb>0)++ans;
			aa=bb=0;
		}
		if(a==k)
			++aa;
		else if(b==k)
			++bb;
		else if(k==-a)
			--aa;
		else if(k==-b)
			--bb;
	}
	cout << ans;
}