CF-1013-(2090)C Dining Hall（小心上界确定问题）

思路讲解

这道题目本身不难，但上界的确定没那么好想

AC代码

源代码

// Problem: C. Dining Hall
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,5> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T,prefer[MAXN];

ll dx[4]={1,2,2,1};
ll dy[4]={1,1,2,2};

bool vis[400][400],visB[2000][2000];

struct cmp{
	bool operator()(const arr &a,const arr &b) const{
		ll xa=a[0],xb=b[0],ya=a[1],yb=b[1],disa=a[4],disb=b[4];
		if(disa!=disb) return disa>disb;
		if(xa!=xb) return xa>xb;
		return ya>yb;
	}
};

// 还是genDis的问题
inline ll genDis(ll fx,ll fy,ll j){
	// if(fx==1 || fy==1) return fx+fy;
	// return fx+fy+2;
	if(j==2) return fx+fy+2;
	return fx+fy;
}

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>prefer[i];
	}
	for(int x=0;x<=sqrtl(2*N)+10;++x){
		for(int y=0;y<=sqrtl(2*N)+10;++y){
			vis[x][y]=false;
			for(int j=0;j<4;++j){
				ll fx=3*x+dx[j],fy=3*y+dy[j];
				visB[fx][fy]=false;
			}
		}
	}
	// pq是用来满足就近原则的东西的
	priority_queue<arr,vector<arr>,cmp> pq,pq1;
	for(int x=0;x<=sqrtl(2*N);++x){
		for(int y=0;y<=sqrtl(2*N);++y){
			vis[x][y]=false;
			for(int j=0;j<4;++j){
				ll fx=3*x+dx[j],fy=3*y+dy[j];
				ll dis=genDis(fx,fy,j);
				pq.push((arr){fx,fy,x,y,dis});
				pq1.push((arr){fx,fy,x,y,dis});
				visB[fx][fy]=false;
			}
		}
	}
	vector<array<ll,2>> ans;
	ll idx=1;
// #ifdef LOCAL
    // cerr << pq.size()<<" "<<pq1.size()<<" "<<N<< '\n';
// #endif
	while(idx<=N){
		if(prefer[idx]){
			while(!pq.empty()){
				ll fx=pq.top()[0],fy=pq.top()[1],x=pq.top()[2],y=pq.top()[3];
				pq.pop();
// #ifdef LOCAL
	// cerr<<"debug1:";
    // cerr << fx<<" "<<fy << '\n';
// #endif
				if(visB[fx][fy]) continue;
				vis[x][y]=true;
				visB[fx][fy]=true;
				ans.pb({fx,fy});
				break;
			}
		}else{
			while(!pq1.empty()){
				ll fx=pq1.top()[0],fy=pq1.top()[1],x=pq1.top()[2],y=pq1.top()[3];
				pq1.pop();
// #ifdef LOCAL
	// cerr<<"debug0:";
    // cerr << fx<<" "<<fy << '\n';
// #endif
				if(vis[x][y]) continue;
				if(visB[fx][fy]) continue;
				visB[fx][fy]=true;
				vis[x][y]=true;
				ans.pb({fx,fy});
				break;
			}
		}
		++idx;
	}
// #ifdef LOCAL
	// cerr<<"debug\n";
	// cerr<<idx<<"\n";
    // cerr << ans.size() << '\n';
// #endif
	for(int i=0;i<ans.size();++i){
		cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

如果上界是$sqrt(N)$ 其实桌子是够的，但是不一定能找到最优解。

通过排布规律我们知道他其实是呈三角形排布，所以要变换上界为$sqrt(2*N)$

for(int x=0;x<=sqrtl(2*N);++x){
		for(int y=0;y<=sqrtl(2*N);++y){
			vis[x][y]=false;
			for(int j=0;j<4;++j){
				ll fx=3*x+dx[j],fy=3*y+dy[j];
				ll dis=genDis(fx,fy,j);
				pq.push((arr){fx,fy,x,y,dis});
				pq1.push((arr){fx,fy,x,y,dis});
				visB[fx][fy]=false;
			}
		}
	}