关于指针(P5021 [NOIP2018 提高组] 赛道修建
  • 板块学术版
  • 楼主CuSO4_and_5H2O
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/11/8 21:39
  • 上次更新2023/10/27 03:41:25
查看原帖
关于指针(P5021 [NOIP2018 提高组] 赛道修建
231946
CuSO4_and_5H2O楼主2022/11/8 21:39

RT,先放代码

#include<bits/stdc++.h>
#define max(A,B) (A<B?B:A)
#define min(A,B) (A>B?B:A)
#define bug cout<<"I AK IOI"<<endl;
#define gc getchar
using namespace std;
const int N=6e4+1;

inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline int read(){int res = 0, f = 0; char ch = gc();for(; !isdigit(ch); ch = gc()) f |= (ch == '-'); for(;isdigit(ch);ch=gc()) res = (res << 1) + (res << 3) + (ch ^ '0');return f ? -res :res;}

struct node{
	int nxt,to,qz;
}e[N*2];int cnt,head[N];
inline void add(int a,int b,int c){e[++cnt].to=b,e[cnt].qz=c,e[cnt].nxt=head[a],head[a]=cnt;}

int n,m,a,b,c,qwq;
int jis=0;

multiset<int > vec[N*2];

inline int dfs(int k,int x,int fa,int kkk)
{
	vec[kkk].clear();
	for(int i=head[x];i;i=e[i].nxt)
	{
		int nxt=e[i].to; if(nxt==fa) continue ;
		int jil=dfs(k,nxt,x,nxt)+e[i].qz;
		if(jil>=k) jis++;
		else vec[kkk].insert(jil);
	}
	int Max=0; 
	while(!vec[kkk].empty())
	{
		auto i=vec[kkk].begin();
		auto it=vec[kkk].lower_bound(k-*i);
		if(it==vec[kkk].begin() && vec[kkk].count(*it)==1) it++;
		if(it!=vec[kkk].end()){ 
			jis++;
			vec[kkk].erase(it);
			vec[kkk].erase(vec[kkk].begin());
//			vec[kkk].erase(vec[kkk].begin());
//			vec[kkk].erase(it);
		}  else Max=max(Max,*i),vec[kkk].erase(i);
	} 
	return Max;
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<n;i++){a=read(),b=read(),c=read();add(a,b,c),add(b,a,c);}
	jis=0;
	int l=1,r=5e8+1,mid,Max=-1;
	while(l<r){
		qwq=0;
		jis=0;
		mid=(l+r)>>1;
		int zzx=dfs(mid,1,0,1);
		if(jis>=m) Max=max(Max,mid),l=mid+1;
		else r=mid-1;
	}
	qwq=0;
	jis=0;
	int zzx=dfs(l,1,0,1);
	if(jis>=m) Max=max(Max,l);
	cout<<Max;
}
 

在本代码中

			vec[kkk].erase(it);
			vec[kkk].erase(vec[kkk].begin());
//			vec[kkk].erase(vec[kkk].begin());
//			vec[kkk].erase(it);

这一段,上下两边的区别是下边RE70分,上边AC,为啥啊?难道不等价吗?it是不可能等于begin的

2022/11/8 21:39
加载中...