萌新刚学oi,re求助
  • 板块P3403 跳楼机
  • 楼主YOKIMIYA
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/11/2 17:49
  • 上次更新2023/11/5 09:12:50
查看原帖
萌新刚学oi,re求助
273468
YOKIMIYA楼主2020/11/2 17:49

第一个点re了,有无dalao帮忙看下

#include<bits/stdc++.h>
#define int long long
#define maxn 1000005
using namespace std;
long long h,ans;
int x,y,z;
void zsort() {
	int f1=min(x,y);
	if(f1>z) {if(x<y) {x=y; y=f1;}}
	else {
		if(f1==x) {
			if(y>z) {x=y; y=z; z=f1;}
			else {x=z; z=f1;}
			}
		else {
			if(x>z) {y=z; z=f1;} 
			else {y=x; x=z; z=f1;}
			}
	}
}
struct edge {
	int x,d;
	edge(){};
	edge(int a,int b) {x=a;d=b;}
	bool operator<(const edge &a) const {
		return d>a.d;}
};
priority_queue<edge> q;
vector<int> e[maxn];
int dis[maxn],vis[maxn];
void work() {
	for(int i=0;i<z;i++) {
		e[i].push_back((i+y)%z);
		e[i].push_back((i+x)%z);
	}
	memset(dis,0x3f,sizeof(dis));
	q.push(edge(1,1));
	dis[1]=1;
	while(!q.empty()) {
		edge tt;
		while(!q.empty()) {
			tt=q.top();
			q.pop();
			if(!vis[tt.x]) break;
		}
		int now=tt.x;
		if(vis[now]) break;
		vis[now]=1;
		int nex=e[now][0];
		if(dis[nex]>dis[now]+y) {
			dis[nex]=dis[now]+y;
			q.push(edge(nex,dis[nex]));
		}
		nex=e[now][1];
		if(dis[nex]>dis[now]+x) {
			dis[nex]=dis[now]+x;
			q.push(edge(nex,dis[nex]));	
		}
	}
}
void outt()
{
	for(int i=0;i<z;i++) 
	if(dis[i]<=h){
		ans+=(h-dis[i])/z+1;
	}
	cout<<ans<<endl;
}

signed main()
{
	cin>>h;
	cin>>x>>y>>z;
	zsort();
	work();
	outt();
}
2020/11/2 17:49
加载中...