关于刚才ABC的C
  • 板块学术版
  • 楼主oldove_laotofu
  • 当前回复4
  • 已保存回复5
  • 发布时间2025/6/28 22:12
  • 上次更新2025/6/29 17:02:55
查看原帖
关于刚才ABC的C
507256
oldove_laotofu楼主2025/6/28 22:12

rt,用了个upper_bound然后T了7个点,时间在2200ms上下浮动,然而方法和题解应该是一致的。。。求dalao解答一下为什么T(大悲)

#include<bits/stdc++.h>
using namespace std;
int T,n,s1,sn,ans;
int s[200005],head;
bool flag;
int main(){
	scanf("%d",&T);
	while(T--){
		flag=0,ans=0; 
		scanf("%d",&n);
		scanf("%d",&s1);s1=-s1;
		for(int i=0;i<n-2;i++){
			scanf("%d",&s[i+head]);
			s[i+head]=-s[i+head];
		}
		scanf("%d",&sn);sn=-sn;
		sort(s+head,s+head+n-2);
		while(1ll*sn<1ll*2*s1){
			int ind=upper_bound(s+head,s+head+n-2,sn>>1)-s-1;
			if(ind>=head&&s[ind]*2<=sn) sn=s[ind],ans++;
			else {
				flag=1;
				break;
			}
		}
		if(flag) printf("-1\n");
		else printf("%d\n",ans+2);
		head+=n-2;
	}
	return 0;
} 
2025/6/28 22:12
加载中...