Painting The Fence(贪心+优先队列)

Painting The Fence(贪心+优先队列)

题目大意:给 m 种数字,一共 n 个,从前往后填,相同的数字最多 k 个在一起,输出构造方案,没有则输出"-1".

解题思路:贪心的思路,优先选择数量多的先填,这样会让最后剩余相同的数字数量最少,所以我们优先选数量最多的两种数字填,最后剩下的(某一种)就填到它前面的位置去,一定是和相同的填在一起,这里就不证明了,自己画下就可以得到。优先队列模拟即可。

AC_Code

 /* */
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <utility>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,1,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9+;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const double eps=0.000001;
const double pi=acos(-1.0); int n,m,k;
int a[],s[]; struct node///重载,从大到小排序
{
int bianhao,num;
bool operator<(const node &a) const {
return num<a.num;
}
}; priority_queue<node>q; int main()
{
while( ~ scanf("%d%d%d",&n,&m,&k))
{
mem0(a);
mem0(s);
while(!q.empty()) q.pop();
for(int i=; i<=m;i++)
{
node cur;
scanf("%d",&cur.num);
cur.bianhao=i;
q.push(cur);
}
int cnt=;
while( !q.empty() )
{
if( q.size()>= )
{
node n1=q.top(); q.pop();
node n2=q.top(); q.pop();
a[cnt++]=n1.bianhao;
a[cnt++]=n2.bianhao;
n1.num--;
n2.num--;
if( n1.num ) q.push(n1);
if( n2.num ) q.push(n2);
}
else
{
if( a[cnt-]!=q.top().bianhao )
{
node cur=q.top();q.pop();
a[cnt++]=cur.bianhao;
cur.num--;
if(cur.num) q.push(cur);
}
break;
}
}
for(int i=; i<cnt&&!q.empty(); i++)
{
if( a[i]==q.top().bianhao )
{
s[i]+=min(q.top().num,k-);
node cur=q.top();q.pop();
cur.num-=min(cur.num,k-);
if( cur.num ) q.push(cur);
else break;
}
}
if( !q.empty()) printf("-1\n");
else
{
for(int i=;i<cnt;i++)
{
for(int j=;j<=s[i]; j++)
{
printf("%d ",a[i]);
}
}
printf("\n");
}
}
return ;
}
上一篇:回调函数(callback)


下一篇:[luogu P2205] [USACO13JAN]画栅栏Painting the Fence