C. Phoenix and Towers
題目鏈接
題目大意
給你n塊石頭每塊高為hi，要求搭成m座塔，并且任意兩座塔的高度之差不會超過x，問是否可行，如過可以將對應的石頭劃分到一個下標中，
思路
題目給的資料范圍就可以說明一定可以搭成的，每塊石頭都小于差x，那么總存在組合使得其差不會超過x，那么如何組合，將每塊的高度存放于set中這樣每次訪問時，就可以先訪問小的元素，每次取出首元素，洗掉首元素，之后將輸入的ai之和壓入set中，這樣可以讓訪問到的元素差值盡可能的小
通過代碼
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define ll long long
//#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define sdf(n) scanf("%lf",&n)
#define pdf(n) printf("%.lf",n)
#define pE printf("\n")
#define ull unsigned long long
#define pb push_back
#define debug(a) cout<<a<<"??"
#define me(a) memset(a,0,sizeof(a))
#define pre(i,beg,en) for(ll i=beg;i<=en;i++)
#define rep(i,beg,en) for(ll i=beg;i>=en;i--)
#define ph push
#define pi pair<ll,ll>
#define fi first
#define se second
#define pq priority_queue<ll>
const ll mod = 1e9 + 7;
ll a[100010],b[100010];
int main(){
ll t;
sl(t);
while(t--){
ll n,m,x,cnt=1;
set<pi>p;
sl(n),sl(m),sl(x);
pre(i,1,n){
sl(a[i]);
if( (ll) p.size() < m){
b[i]=cnt;
p.insert({a[i],cnt++});
}
else {
auto node=p.begin();
p.erase(*node);
pi y=*node;
y.fi+=a[i];
b[i]=y.se;
p.insert(y);
}
}
puts("YES");
for(ll i=1;i<=n;i++)cout<<b[i]<<' ';
puts("");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/282927.html
標籤：其他
上一篇：Android okhttp使用