当前位置：首页 > news >正文

三分/01分数规划

news 2025/8/17 8:43:01

三分

最小球覆盖 2018南京D
三分套三分套三分

constexpr int N=105;
struct node{int x,y,z;
}a[N];
int n;
double road(double x1,double y1,double z1,double x2,double y2,double z2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
double check(double x,double y,double z){double maxn=0;for (int i=1;i<=n;i++){maxn=std::max(maxn,road(x,y,z,a[i].x,a[i].y,a[i].z));}return maxn;
}
double check(double x,double y){double l=-100000,r=100000,ans=1e18;for (int i=1;i<=80;i++){double mid1=l+(r-l)/3,mid2=r-(r-l)/3;double res1=check(x,y,mid1),res2=check(x,y,mid2);if (res1<res2){r=mid2;}else{l=mid1;}ans=std::min(ans,std::min(res1,res2));}return ans;
}
double check(double x){double l=-100000,r=100000,ans=1e18;for (int i=1;i<=80;i++){double mid1=l+(r-l)/3,mid2=r-(r-l)/3;double res1=check(x,mid1),res2=check(x,mid2);if (res1<res2){r=mid2;}else{l=mid1;}ans=std::min(ans,std::min(res1,res2));}return ans;
}
void yrzr(){std::cin>>n;for (int i=1;i<=n;i++){std::cin>>a[i].x>>a[i].y>>a[i].z;}double l=-100000,r=100000,ans=1e18;for (int i=1;i<=80;i++){double mid1=l+(r-l)/3,mid2=r-(r-l)/3;// std::cout<<std::fixed<<std::setprecision(5)<<mid1<<" "<<mid2<<"\n";double res1=check(mid1),res2=check(mid2);if (res1<res2){r=mid2;}else{l=mid1;}ans=std::min(ans,std::min(res1,res2));}std::cout<<std::fixed<<std::setprecision(5)<<ans;
}

P2571 [SCOI2010] 传送带
感性理解一下，从 $ab$ 传送带到 $c d$ 传送带，每个传送带只有一个点出发/到达是最优的，所以单峰，满足三分性

int ax,ay,bx,by,cx,cy,dx,dy;
int p,q,r;
double road(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double check(double x,double y){double lx=cx,ly=cy,rx=dx,ry=dy,ans=1e18;for (int i=1;i<=100;i++){double mid1x=(2*lx+rx)/3,mid1y=(2*ly+ry)/3;double mid2x=(lx+2*rx)/3,mid2y=(ly+2*ry)/3;double res1=road(dx,dy,mid1x,mid1y)/q+road(x,y,mid1x,mid1y)/r;double res2=road(dx,dy,mid2x,mid2y)/q+road(x,y,mid2x,mid2y)/r;if (res1>res2){lx=mid1x;ly=mid1y;}else{rx=mid2x;ry=mid2y;}ans=std::min(ans,res1);}return ans;
}
void yrzr(){std::cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy>>p>>q>>r;double lx=ax,ly=ay,rx=bx,ry=by,ans=1e18;for (int i=1;i<=100;i++){double mid1x=(2*lx+rx)/3,mid1y=(2*ly+ry)/3;double mid2x=(lx+2*rx)/3,mid2y=(ly+2*ry)/3;double res1=road(ax,ay,mid1x,mid1y)/p+check(mid1x,mid1y);double res2=road(ax,ay,mid2x,mid2y)/p+check(mid2x,mid2y);if (res1>res2){lx=mid1x;ly=mid1y;}else{rx=mid2x;ry=mid2y;}ans=std::min(ans,res1);}std::cout<<std::fixed<<std::setprecision(2)<<ans;
}

[SHOI2017]期末考试
从小到大排序，三分最后出成绩的时间，然后贪心，将晚出的学科进行操作
时间复杂度通过前缀和预处理可以做到 $O(nlogn+log^2n)$

注意测试点C==1e16时会炸longlong，进行特判

constexpr int N=1e5+5;
int A,B,C,n,m;
int t[N],b[N],sum[N],tol[N];
int check(int dl){if (b[m]<=dl){return 0;}int pos=std::upper_bound(b+1,b+1+m,dl)-b;int sum1=dl*(pos-1)-tol[pos-1],sum2=(tol[m]-tol[pos-1])-(m-pos+1)*dl;if (B<=A){return sum2*B;}else{if (sum1>=sum2){return sum2*A;}else{return sum1*A+(sum2-sum1)*B;}}
}
void yrzr(){std::cin>>A>>B>>C>>n>>m;for (int i=1;i<=n;i++){std::cin>>t[i];}for (int i=1;i<=m;i++){std::cin>>b[i];}std::sort(t+1,t+1+n);for (int i=1;i<=n;i++){sum[i]=sum[i-1]+t[i];}std::sort(b+1,b+1+m);for (int i=1;i<=m;i++){tol[i]=tol[i-1]+b[i];}if (C==1e16){std::cout<<check(t[1]);return;}int ans=1e18;int l=0,r=100000,res1,res2;while (l<r){int mid1=(2*l+r)/3,mid2=(l+2*r)/3;int pos1=std::upper_bound(t+1,t+1+n,mid1)-t-1;int pos2=std::upper_bound(t+1,t+1+n,mid2)-t-1;res1=(mid1*pos1-sum[pos1])*C+check(mid1);res2=(mid2*pos2-sum[pos2])*C+check(mid2);if (res1>res2){l=mid1+1;}else{r=mid2-1;}ans=std::min(ans,std::min(res1,res2));// std::cout<<mid1<<" "<<res1<<" "<<mid2<<" "<<res2<<"\n";}std::cout<<ans;
}

分数规划

小咪买东西
板子

void yrzr(){int n,k;std::cin>>n>>k;std::vector<int> c(n+1),v(n+1);for (int i=1;i<=n;i++){std::cin>>c[i]>>v[i];}int l=0,r=1e9,ans=0;auto check=[&](int x){std::vector<int> temp;for (int i=1;i<=n;i++){temp.push_back(v[i]-c[i]*x);}std::sort(temp.begin(),temp.end(),[&](int i,int j){return i>j;});int sum=0;for (int i=0;i<k;i++){sum+=temp[i];}return (sum>=0?1:0);};while (l<=r){int mid=(l+r)>>1;if (check(mid)){l=mid+1;ans=mid;}else{r=mid-1;}}std::cout<<ans<<"\n";
}

gpa
转换一下，其实就是买的物品个数变成了一个范围 $[n - k, n]$
$c h ec k$ 的时候，一旦出现一个满足范围且 $s u m >= 0$ 的时候就是合法的

void yrzr(){int n,k;std::cin>>n>>k;std::vector<int> s(n+1),c(n+1);for (int i=1;i<=n;i++){std::cin>>s[i];}for (int i=1;i<=n;i++){std::cin>>c[i];c[i]*=s[i];}double l=0,r=1e9,ans=0;auto check=[&](double x){std::vector<double> temp;for (int i=1;i<=n;i++){temp.push_back(c[i]-x*s[i]);}std::sort(temp.begin(),temp.end(),[&](int i,int j){return i>j;});double sum=0;for (int i=1;i<=n;i++){sum+=temp[i-1];if (sum>0&&n-i<=k){return 1;}}return 0;};for (int i=1;i<=60;i++){double mid=(l+r)/2;if (check(mid)){l=mid+1;ans=mid;}else{r=mid-1;}}std::cout<<std::fixed<<std::setprecision(8)<<ans;
}

P4377 [USACO18OPEN] Talent Show G
与之前不同的是，此题没有限制选的数量，而是限制分母的和，二分完后，转换为背包问题即可

void yrzr(){int n,W;std::cin>>n>>W;std::vector<int> w(n+1),t(n+1);for (int i=1;i<=n;i++){std::cin>>w[i]>>t[i];t[i]*=1000;}int l=0,r=1e9,ans=0;auto check=[&](int x){std::vector<int> c(n+1),v(n+1);for (int i=1;i<=n;i++){c[i]=t[i]-w[i]*x;v[i]=w[i];}std::vector<int> f(W+1,-1e18);f[0]=0;for (int i=1;i<=n;i++){for (int j=W;j>=0;j--){f[std::min(W,j+v[i])]=std::max(f[std::min(W,j+v[i])],f[j]+c[i]);}}return (f[W]>=0?1:0);};while (l<=r){int mid=(l+r)/2;if (check(mid)){l=mid+1;ans=mid;}else{r=mid-1;}}std::cout<<ans<<"\n";
}