只过了6个点,来组数据hack一下
查看原帖
只过了6个点,来组数据hack一下
230808
Zxsoul楼主2021/3/27 19:40
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e7+10;
const int B = 1e4+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

struct node{int l,r,id,rid,flag,pt;}a[B];
int n,k,b[B],cnt;

main()
{
	int x;
	n=read();k=read();
	b[0]=inf;
	int js=0,p=0,top=1;
	for (int i=1;i<=n;i++)
	{
		b[i]=read();
//		if (p==0 && b[i]==0) {top=i;p=1;}
		if (b[i]==1) js++;
		else if (b[i]==0) 
		{
			a[cnt+1].id=cnt;
			a[++cnt].l=js;
			a[cnt].pt=i;
//			a[cnt].id=top;
//			top=i;
			js=0;		
		}
	}
	int s=cnt;
	p=0,top=n,js=0;
	for (int i=n;i>=1;i--)
	{
//		if (p==0 && b[i]==0) {top=i;p=1;}
		if (b[i]==1) js++;
		if (b[i]==0)
		{
			a[s-1].rid=s;
			a[s--].r=js;
//			a[s--].rid=top;
//			top=i;
			js=0;
		}
	}
	
		for (int j=1;j<=k;j++)
		{
			int id,cmp=0,s=cnt;
			for (int i=cnt;i>=1;i--)
			{
				if (cmp<a[i].l) {cmp=a[i].l,id=i;}
				if (cmp<a[i].r) {cmp=a[i].r,id=i;}
			}
			int ID=a[id].id;
			int rr=a[id].rid;
			a[ID].r+=(a[id].r+1);
			a[ID].rid=a[id].rid;
			a[rr].l+=(a[id].l+1);
			a[rr].id=a[id].id;
			a[id].flag=1;
		}
	for (int i=1;i<=cnt;i++) if(a[i].flag==1) b[a[i].pt]=1;
	int ans=0;
	js=0;
	for (int i=1;i<=n;i++)
	{
		if (b[i]==1) js++;
		if (b[i]==0) 
		{
			ans=max(ans,js);
			js=0;
		}
	}
	ans=max(js,ans);
	printf("%lld\n",ans);
	for (int i=1;i<=n;i++) printf("%lld ",b[i]);
}
2021/3/27 19:40
加载中...