a450 - 棒棒糖比身高

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定一個棒棒糖高度的陣列，對於每個查詢區間 [l, h]，輸出高度介於 l 和 h (包含 l 和 h) 之間的棒棒糖數量。如果沒有符合條件的棒棒糖，則輸出 "The candies are too short"。

解題思路

首先，對棒棒糖高度陣列進行排序。對於每個查詢區間 [l, h]，使用 lower_bound 找到第一個大於等於 l 的棒棒糖位置，使用 upper_bound 找到第一個大於 h 的棒棒糖位置。兩個位置之間的差值即為高度在 [l, h] 範圍內的棒棒糖數量。如果差值為 0，則表示沒有符合條件的棒棒糖，輸出 "The candies are too short"。

複雜度分析

• 時間複雜度: O(n log n + q log n) (排序陣列 O(n log n)，每個查詢使用二分查找 O(log n)，總共 q 個查詢)
• 空間複雜度: O(n) (用於儲存棒棒糖高度陣列)

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,q,l,h;
	cin >> n >> q;
	int a[n];
	for(int i=0;i<n;++i)
		cin >> a[i];
	sort(a,a+n);
	while(q--){
		cin >> l >> h;
		int ans=upper_bound(a,a+n,h)-lower_bound(a,a+n,l);
		(ans==0)?cout << "The candies are too short\n":cout << ans << "\n";
	}
}