emu1

第一题

一个很奇怪的贪心。先排序一遍，再扫描一遍，能加入尽量加入，不能加入就一定不能加入。。由于每次都在可能的最早时间加入一个数可以保证差最小？反正差不多这样了。

O(n log n)

#include <cstdio>

#include <algorithm>

bool cmp(int a,int b){

	return a>b;

}

int m,n,i,j,k,f[200000],g[200000];

int sumn,sumd;

int main(){

	freopen("stockman.in","r",stdin);

	freopen("stockman.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(i=0;i<n;++i) scanf("%d",f+i);

	for(i=0;i<m;++i) scanf("%d",g+i);

	std::sort(f,f+n);

	std::sort(g,g+m);

	i=n-1;j=m-1;

	while(i>=0 && j>=0){

		//while using the jth stockman trying to match the ith pig

		if(f[i]>=g[j]){

			if(!(i&&j)||f[i-1]<=g[j]||f[i-1]>=g[j-1]){

				++sumn;

				sumd+=f[i]-g[j];

				--i;

				--j;

				continue;

			}

			--i;

		}else{

			--j;

		}

	}

	printf("%d\n%d\n",sumn,sumd);

	return 0;

}

似乎有个更好的堆的解法？

#include <cstdio>

#include <queue>

#include <algorithm>

std::priority_queue<int> q;

int m,n,i,j,k,f[200000],g[200000];

int sumn,sumd;

int main(){

	freopen("stockman.in","r",stdin);

	freopen("stockman.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(i=0;i<n;++i) scanf("%d",f+i);

	for(i=0;i<m;++i) scanf("%d",g+i);

	std::sort(f,f+n);

	std::sort(g,g+m);

	for(i=0;i<n;++i){

		while(f[i]>=g[j] && j<m){

			q.push(g[j]);

			++j;

		}

		if(!(q.empty())){

			++sumn;

			sumd+=f[i]-q.top();

			q.pop();

		}

	}

	printf("%d\n%d\n",sumn,sumd);

	return 0;

}

第二题。。

先BFS一遍求出每个点与最近的敌人的距离，再二分答案能否到达，BFS求距离。

O(log{max(dis)==2000}mn)最沙茶的数据也可以过吧。。

#include <cstdio>

#include <cstring>

int qx[8000000],qy[8000000],qh,qt;

int f[2000][2000],m,n,i,j,k,x,y,x1,x2,y1,y2;

bool accessed[2000][2000];

char ch;

int left,right,mid,ans,ansl;

int minl[2000][2000];

inline void relax(int x,int y,int v){

	if(accessed[x][y]) return;

	if(x<0 || y<0 || x==n || y==m) return;

	f[x][y]=v;

	accessed[x][y]=true;

	qx[qt]=x;

	qy[qt++]=y;

}

inline void relax2(int x,int y,int v,int l){

	if(accessed[x][y] || f[x][y]<l) return;

	if(x<0 || y<0 || x==n || y==m) return;

	minl[x][y]=v;

	accessed[x][y]=true;

	qx[qt]=x;

	qy[qt++]=y;

}

bool check(int least){

	memset(accessed,0,sizeof accessed);

	qh=qt=0;

	qx[qt]=x1;

	qy[qt++]=y1;

	minl[x1][y1]=0;

	accessed[x1][y1]=true;

	while(qh!=qt){

		x=qx[qh];

		y=qy[qh++];

		i=minl[x][y]+1;

		relax2(x,y+1,i,least);

		relax2(x,y-1,i,least);

		relax2(x+1,y,i,least);

		relax2(x-1,y,i,least);

	}

	return accessed[x2][y2];

}

int main(){

	freopen("escape.in","r",stdin);

	freopen("escape.out","w",stdout);

	scanf("%d%d%d%d%d%d%d",&k,&n,&m,&x1,&y1,&x2,&y2);

	for(i=0;i<k;++i){

		scanf("%d%d",&x,&y);

		qx[qt]=x;

		qy[qt++]=y;

	}

	while(qh!=qt){

		x=qx[qh];

		y=qy[qh++];

		i=f[x][y]+1;

		relax(x,y+1,i);

		relax(x,y-1,i);

		relax(x+1,y,i);

		relax(x-1,y,i);

	}

	left=0;right=f[x1][y1];

	while(left<=right){

		mid=(left+right)/2;

		if(check(mid)){

			left=mid+1;

			ans=mid;

			ansl=minl[x2][y2];

		}else{

			right=mid-1;

		}

	}

	printf("%d %d\n",ans,ansl);

	return 0;

}

第三题

orz WJZ神犇的双参数SPFA。

______________________________________________________________________

巴特西

emu1

最新文章

热门文章