紫贪心SPJ求条
查看原帖
紫贪心SPJ求条
1546551
OIer_forget114514楼主2025/7/25 12:04
#include <bits/stdc++.h>
using namespace std;
#define I cin >>
#define O cout <<
#define int long long
#define PII pair<int,int>
char ch[805][805];
int n,m,k,l,d[805][805],day=1,a[805],tot,res[805][805],vis[805],is;
priority_queue<PII,vector<PII>,greater<PII> > q;
bool cmp(int x,int y){
	return d[x][day]>d[y][day];
}
signed main(){
	I n >> m >> k >> l;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) I ch[i][j];
		for(int j=m;j>=1;j--){
			if(ch[i][j]=='1') d[i][j]=d[i][j+1]+1;
			else d[i][j]=0;
		}
	}
	while(day<=m){
		tot=0;
		for(int i=1;i<=n;i++){
			if(d[i][day]&&(!vis[i])) a[++tot]=i;
		}
		sort(a+1,a+tot+1,cmp);
		if(day==1){
			for(int i=1;i<=k&&i<=tot;i++) q.push(make_pair(day+d[a[i]][day]-1,a[i])),res[day][i]=a[i],vis[a[i]]=1;
		}else{
			while(!q.empty()&&q.top().first<day) vis[q.top().second]=0,q.pop();
			for(int i=1;i<=l&&i<=tot;i++){
				if(q.size()+i>k) vis[q.top().second]=0,q.pop();
				q.push(make_pair(day+d[a[i]][day]-1,a[i]));
				vis[a[i]]=1;
			} 
			int tt=0;
			for(int i=1;i<=n;i++){
				if(vis[i]) res[day][++tt]=i;
			}
		}
		if(q.size()<k){
			is=1;
			break;
		}
		day++;
	}
	if(is){
		O "-1";
		return 0;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=k;j++){
			O res[i][j] << " ";
		}
		O "\n";
	}
	return 0;
}

题目WA,只得了10分

2025/7/25 12:04
加载中...