c177 - 合唱隊面試
題目描述
題目要求找出最小的 p，使得從前 p 個人中可以選出 m 個人，且任意兩人身高差不超過 k。如果無法從所有 n 個人中選出符合條件的 m 個人，則輸出 "Impossible"。
解題思路
本題可以使用滑動視窗的概念來解決。我們遍歷每個人的身高，並使用一個陣列 c 來記錄每個身高出現的次數。對於每個人的身高 a[i]，我們將 c[j] (j 從 0 到 a[i]) 的值加 1。然後，我們檢查是否存在一個長度為 k+1 的視窗，使得視窗內的人數大於等於 m。具體來說，我們遍歷 j 從 0 到 200-k，檢查 c[j] - c[j+k+1] 是否大於等於 m。如果找到這樣的視窗，則表示我們可以在前 i+1 個人中選出 m 個人，因此輸出 i+1 並結束程式。如果遍歷完所有人的身高後仍然找不到符合條件的 p，則輸出 "Impossible"。
複雜度分析
- 時間複雜度: O(n * k)
- 空間複雜度: O(201)
程式碼
#include <iostream>
using namespace std;
int n,m,k,a[10005],c[202],ac;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m >> k;
for(int i=0;i<n;++i){
cin >> a[i];
}
for(int i=0;i<n&&ac==0;++i){
for(int j=0;j<=a[i];++j){
c[j]++;
//cout << c[j] << " ";
}
//cout << "\n";
for(int j=0;j<=200-k;++j){
if(c[j]-c[j+k+1]>=m){
ac=1;
break;
}
}
if(ac){
cout << i+1;
}
}
if(ac==0){
cout << "Impossible";
}
}