a014 - 夾娃娃
題目描述
題目描述一個一維空間的夾娃娃遊戲。給定 N 個娃娃的位置範圍 [A, B] 和夾子寬度 Y，要求找到最佳的夾取地點 C，使得夾起的娃娃數量最多。如果有多個 C 值可以夾到相同數量的娃娃，則輸出這些 C 值的個數以及最大娃娃數量。
解題思路
本題的核心思想是枚舉夾子的左端坐標 C，然後計算在 C 到 C+Y 的範圍內可以夾到的娃娃數量。為了提高效率，可以使用 Binary Indexed Tree (BIT) 來快速計算在某個範圍內有多少個娃娃。
- 輸入處理： 讀取 N 和 Y，以及每個娃娃的位置範圍 [A, B]。
- BIT 初始化： 使用 BIT 記錄每個位置是否有娃娃。對於每個娃娃，將 BIT 中對應位置的值加 1。
- 排序： 將娃娃的位置範圍按照起始位置 A 排序。
- 枚舉夾子位置： 枚舉夾子的左端坐標 C，從 1 到 MAXN/2。
- 更新 BIT： 在枚舉過程中，如果當前位置 C 超過了某個娃娃的起始位置 A，則將該娃娃從 BIT 中移除。
- 計算夾取數量： 使用 BIT 計算在 C 到 C+Y 的範圍內可以夾到的娃娃數量。
- 更新答案： 如果當前夾取數量大於最大夾取數量，則更新最大夾取數量和最佳夾取地點的個數。如果當前夾取數量等於最大夾取數量，則增加最佳夾取地點的個數。
複雜度分析
- 時間複雜度: O(N log M + M/2 * log M)，其中 N 是娃娃的數量，M 是娃娃位置的最大值。排序需要 O(N log N)，BIT 的更新和查詢需要 O(log M)，枚舉夾子位置需要 O(M/2)，因此總時間複雜度為 O(N log N + M/2 * log M)。
- 空間複雜度: O(M)，主要用於儲存 BIT。
程式碼
#include <iostream>
#include <algorithm>
#define MAXN 200000
using namespace std;
int BIT[200005],n,m;
pair <int,int> a[30005];
int lb(int x){
return x&(-x);
}
void edit(int x,int v){
for(int i=x;i<=MAXN;i+=lb(i)){
BIT[i]+=v;
}
}
int sum(int x){
int rt=0;
for(int i=x;i>0;i-=lb(i)){
rt+=BIT[i];
}
return rt;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
int ma=0,ans=0,la=-1,it=0,tmp;
for(int i=0;i<=MAXN;++i){
BIT[i]=0;
}
for(int i=0;i<n;++i){
cin >> a[i].first >> a[i].second;
edit(a[i].second,1);
}
sort(a,a+n);
for(int i=1;i<=MAXN/2;++i){
while(it<n&&i>a[it].first){
edit(a[it].second,-1);
++it;
}
tmp=sum(i+m);
if(tmp==ma){
++ans;
}
else if(tmp>ma){
ans=1;
ma=tmp;
}
}
cout << ans << " " << ma << "\n";
}
}