g310 - pD. 甜甜圈大對決(Donut)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了兩家甜甜圈店 x 和 y 之間的比賽。店 x 按照從小到大的順序派出 N 個甜甜圈，店 y 可以從 N 個甜甜圈中選擇派出，目標是讓店 y 贏得最多比賽。

解題思路

由於店 x 的甜甜圈是按照從小到大的順序派出的，店 y 為了最大化勝利場數，應該總是派出比店 x 當前甜甜圈更大的最小甜甜圈。 程式碼中，ans 追蹤店 y 已經贏得的比賽數量。 迴圈遍歷每個比賽，如果店 y 的當前甜甜圈值大於店 x 的甜甜圈值，則 ans 增加。 由於 y 的甜甜圈已經排序，因此可以簡單地比較 k > a[ans]。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
long long n,a[1000001],k,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a[i];
	}
	for(int i=0;i<n;++i){
		cin >> k;
		if(k>a[ans])++ans;
	}
	cout << ans;
}