2024.2.19

Bear and Paradox

你在打比赛，题 \(i\) 的初始分值为 \(a_i\)，须时间 \(t_i\) 做出，在时间 \(x\) 做出题 \(i\) 的得分为 \(b_i=a_i\cdot (1-c\cdot \frac{x}{T})\)，其中 \(c\) 为 \([0,1]\) 间的常数，\(T=\sum t_i\)。

找到最大的 \(c\)，使得在所有总得分最大的情况下， \(\not\exist (i,j)\)，有 \(a_i>a_j\) 且 \(b_i<b_j\)。

\(n\le 1.5\times 10^5\)，\(1\le a_i,t_i\le 10^8\)，精度要求 \(10^{-6}\)。

调整法可得 \(\dfrac{a_i}{t_i}\) 大的排在前面。问题是我们要将 \(\dfrac{a_i}{t_i}\) 相同的排序以构造最劣解。

然后乱搞发现把最大的放在最后面，次大的放在第一个就好了，这是可以感性理解的。

二分 \(c\)，时间复杂度 \(O(n\cdot |\log \epsilon|)\)，我脑抽加了个 BIT 也是没啥问题的。

#include<bits/stdc++.h>
#define ll long long
#define db double
#define N 200010
#define eps 1e-8
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
struct dat{
	int a,t;
	bool operator<(const dat &x)const{
		return 1ll*a*x.t>1ll*x.a*t;
	}
}b[N];
int n;ll T;
db s[N];int a[N],t[N];
priority_queue<pii>q;
struct BIT{
	#define lb(x) x&-x
	db c[N];
	void clr(){for(int i=0;i<=n;i++)c[i]=0;}
	void add(int x,db k){
		for(;x<=n;x+=lb(x))c[x]=max(c[x],k);
	}
	db qry(int x){
		db ret=0;
		for(;x;x-=lb(x))ret=max(ret,c[x]);
		return ret;
	}
}B;
int tp[N],len,aa[N];
void lsh(){
	for(int i=1;i<=n;i++)tp[i]=a[i];
	sort(tp+1,tp+1+n),len=unique(tp+1,tp+1+n)-tp-1;
	for(int i=1;i<=n;i++)
		aa[i]=lower_bound(tp+1,tp+1+len,a[i])-tp;
}
bool check(db c){
	c/=T;ll sum=0;B.clr();
	for(int i=1;i<=n;i++){
		sum+=t[i],s[i]=(db)a[i]*(1.0-c*sum);
		B.add(aa[i],s[i]);
	}
	for(int i=1;i<=n;i++)
		if(B.qry(aa[i]-1)>s[i])return false;
	return true;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)b[i].a=read();
	for(int i=1;i<=n;i++)T+=(b[i].t=read());
	sort(b+1,b+1+n);
	q.push(mp(b[1].a,b[1].t));
	for(int i=1,l=1;i<=n;i++){
		while(i<n&&1ll*b[i].a*b[i+1].t==1ll*b[i].t*b[i+1].a)
			q.push(mp(b[i+1].a,b[i+1].t)),i++;
		a[i]=q.top().fi,t[i]=q.top().se,q.pop();
		if(!q.empty())a[l]=q.top().fi,t[l]=q.top().se,q.pop();
		for(int j=l+1;j<i;j++)
			a[j]=q.top().fi,t[j]=q.top().se,q.pop();
		l=i+1,q.push(mp(b[l].a,b[l].t));
	}
	lsh();
	db l=0,r=1,mid,ans=0;
	while(l+eps<r){
		mid=(l+r)/2.0;
		if(check(mid))ans=mid,l=mid;
		else r=mid;
	}
	printf("%.10lf\n",ans);

	return 0;
}

JZOJ 6701. 旅行

你在极大二维平面上移动，要从 \((sx,sy)\) 到 \((tx,ty)\)。

有 \(n\) 个矩形障碍物，左下角 \((a_i,b_i)\)，右上角 \((c_i,d_i)\)。障碍物间不交且无公共点。

你只能平行于坐标轴移动，不能进入障碍物，但可以沿着障碍物边缘行动。问最少步数。

\(n\le 2\times 10^5\)，\(0\le sx,sy,tx,ty,a_i,b_i,c_i,d_i\le 10^8\)，所有横坐标两两不同，所有纵坐标两两不同。

JZOJ 6702. 仙人掌

求仙人掌的邻接矩阵的行列式的值。

\(n\le 10^5\)，\(m\le 2\times 10^5\)。