• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

C. Phoenix and Towers

互联网 diligentman 1周前 (05-04) 7次浏览

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;
}


程序员灯塔
转载请注明原文链接:C. Phoenix and Towers
喜欢 (0)