題目連結: https://codeforces.com/problemset/problem/1380/C
# 內容
有 N 個人要分組,每個人若有組則只參加一組,每個人有技能值 ai , 組隊要求為:組員人數與組員中最低技能值的乘積要不小於 x。問最多可以分幾組。
# 思路
要分最多組肯定是每組的人數越少越好。當人數越少時,為了滿足限制,則需要組內最低技能值高,因此從大到小遍歷所有人,判斷當前人數和最低技能值的乘積是否夠組成一個組。
# 程式碼
#include <bits/stdc++.h> | |
#define int long long | |
using namespace std; | |
bool cmp(int x, int y){return x > y;} | |
signed main(){ | |
int t; cin>>t; | |
while(t--){ | |
int n,x; | |
cin>>n>>x; | |
vector<int> a(n); | |
for(int i = 0;i<n;i++)cin>>a[i]; | |
sort(a.begin(), a.end(), cmp); | |
int ans = 0; | |
for(int i = 0; i < n; ){ | |
int l, r; | |
l = r = i; | |
int tmp = 1,cnt = 1; | |
int Min = a[r]; | |
while(r < n){ | |
tmp = Min * cnt; | |
if(tmp >= x) break; | |
cnt++; r++; | |
Min = a[r]; | |
} | |
if(tmp >= x) ans++; | |
i = r + 1; | |
} | |
cout<<ans<<endl; | |
} | |
return 0; | |
} |