主要以题为主咯

习题1 POJ 1064 Cable master

题意：给出n条绳子，想切出m段，问最长多长（向下取整）

题解

二分切出来的长度，然后O(N)check即可

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=10005; #define EPS 1e-8 double p[N]; int n,k; bool check(double x){ int sum=0; for(int i=1;i<=n;i++){ sum+=int(p[i]/x); } return sum>=k; } int main() { scanf("%d%d",&n,&k); double l,r,mid; l=0; for(int i=1;i<=n;i++){ scanf("%lf",&p[i]); if(i==1){ r=p[i]; } else r=max(r,p[i]); } while(r-l>EPS){ mid=(l+r)/2; if(check(mid)){ l=mid; } else{ r=mid; } } l+=EPS; printf("%.2lf",floor(l*100)/100); }

习题2 POJ 2456 Aggressive cows

题意：x轴上N个点，从中选择M个点，使得点之间最小的距离最大

题解

二分最小距离，O(M)check

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=100005; int a[N]; int n,k; bool check(int x){ int sum=1; int past=a[1]; for(int i=2;i<=n&&sum<k;i++){ if(a[i]-past>=x){ past=a[i]; sum++; } } return sum==k; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); int l=1,r=a[n]-a[1]; while(l+1<r){ int mid=(l+r)>>1; if(check(mid)) l=mid; else r=mid; } printf("%d\n",l); }

习题2’ POJ 3258 River Hopscotch

题意：河中有N块石头，问移除M块石头后，跳跃距离最少是多少

题解

注意考虑岸

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=50005; int p[N]; int ans=0; int n,m; bool OK(int d){ int now=1; int past=0; int tot=0; while(tot<=m&&now<=n){ if(p[now]-p[past]<d) tot++; else past=now; now++; } if(tot<=m){ ans=max(ans,d); return true; } else return false; } int main() { int l=0,r; scanf("%d%d%d",&r,&n,&m); if(m>=n){ printf("%d",r); return 0; } for(int i=1;i<=n;i++) scanf("%d",&p[i]); sort(p+1,p+n+1); n++; p[n]=r; while(l<r){ int mid=(l+r)>>1; if(OK(mid)) l=mid+1; else r=mid; } printf("%d\n",ans); }

习题3 POJ 2976 Dropping tests

题意：给出N组数，删去M组，求剩下的分子相加/分母相加的最大值（百分数）

题解

设分子为v,分母为w，二分出的答案为x 则我们是要求

∑vi∑wi≥x ∑ v i ∑ w i ≥ x 即 ∑vi−x⋅wi≥0 ∑ v i − x · w i ≥ 0 那么，我们就可以二分枚举x，然后将其他数按 vi−x⋅wi v i − x · w i 排序，贪心的选出n-m个，判断能否大于等于0即可

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=100005; const int INF=1<<30; #define EPS 1e-6 int n,k; struct node{ double x,y; double d; }p[N]; bool cmp(node a,node b){ return a.d>b.d; } bool check(double x){ for(int i=1;i<=n;i++){ p[i].d=p[i].x-x*p[i].y; } sort(p+1,p+n+1,cmp); double sum=0; for(int i=k;i>=1;i--){ sum+=p[i].d; if(sum>=0) return true; } return sum>=0; } int main() { while(~scanf("%d%d",&n,&k)){ if(n==0&&k==0) return 0; k=n-k; for(int i=1;i<=n;i++) scanf("%lf",&p[i].x); for(int i=1;i<=n;i++) scanf("%lf",&p[i].y); double l=0,r=1; double mid; while(r-l>EPS){ mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.0lf\n",(l+EPS)*100); } }

习题3’ POJ 3111 K Best

题意：给出N组数，保留M组，求使分子相加/分母相加的最大需要保留哪几组，如果有多解，输出任意一个

题解

基本同习题3

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define EPS 1e-6 const int N=100005; struct node{ double v,w,d; int pos; }p[N]; bool cmp(node a,node b){ return a.d>b.d; } int n,k; int ans[N]; bool check(double x){ for(int i=1;i<=n;i++){ p[i].d=p[i].v-p[i].w*x; } sort(p+1,p+n+1,cmp); double y=0; for(int i=k;i>0;i--){ y+=p[i].d; if(y>=0) return true; } return false; } int main() { scanf("%d%d",&n,&k); double l=0,r=1e7+5,mid; for(int i=1;i<=n;i++){ scanf("%lf%lf",&p[i].v,&p[i].w); p[i].pos=i; } while(r-l>EPS){ mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } sort(p+1,p+n+1,cmp); for(int i=1;i<=k;i++) ans[i]=p[i].pos; sort(ans+1,ans+k+1); for(int i=1;i<=k;i++) printf("%d ",ans[i]); }

习题4 POJ 3273 Monthly Expense

题意：有N个数，分成M组（只有连续的才能被分到一起），问这些组最大的和最小是多少

题解

二分和，O(N)check

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100005; int a[N]; int n,k; bool check(int x){ int r=x; int j=1; for(int i=1;i<=n&&j<=k;i++){ if(a[i]<=r) r-=a[i]; else{ j++; r=x-a[i]; } } return j<=k; } int main() { scanf("%d%d",&n,&k); int l=0,r=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); l=max(l,a[i]); r+=a[i]; } int mid; while(l<r){ mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d\n",r); }

习题5 POJ 3104 Drying

题意：有N件衣服，每件衣服有一个湿度值，有一个烘干机，每单位时间蒸发K单位的水，还可以自然风干，每单位时间1单位的水，问最少需要几单位的时间能把衣服都烘干

题解

二分枚举答案x，记录一个sum，枚举每个衣服，如果说湿度值<=x就不用管，否则

sum+=⌈ti−xk−1⌉ s u m + = ⌈ t i − x k − 1 ⌉ 因为我们想尽可能少用烘干机，所以并不是 sum+=⌈tik⌉ s u m + = ⌈ t i k ⌉ 注意到k-1在分母，所以需要特判一下，此时答案就是最大湿度值

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const long long N=100005; long long t[N],n,k; bool check(long long x){ long long sum=0; for(long long i=1;i<=n;i++){ if(t[i]>x) sum+=(t[i]-x)/(k-1)+((t[i]-x)%(k-1)!=0); } return sum<=x; } int main() { scanf("%lld",&n); long long l=1,r=0; for(long long i=1;i<=n;i++){ scanf("%lld",&t[i]); r=max(r,t[i]); } scanf("%d",&k); if(k==1){ printf("%lld\n",r); return 0; } long long mid; while(l<r){ mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%lld\n",r); }

习题6 POJ 3579 Median

http://poj.org/problem?id=3579

题解

二分答案+二分查找

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=1000005; #define EPS 1e-6 long long a[N]; long long n,m; int Find(int x){ int l=1,r=n+1; while(l+1<r){ int mid=(l+r)>>1; if(a[mid]>x) r=mid; else l=mid; } return r; } bool check(int x){ long long sum=0; for(int i=1;i<=n;i++){ int y=n-Find(a[i]+x)+1; if(y==0) break; sum+=y; } return sum<=m; } int main() { while(~scanf("%I64d",&n)){ for(int i=1;i<=n;i++){ scanf("%I64d",&a[i]); } sort(a+1,a+n+1); m=(n*(n-1)/2)/2; int l=0,r=a[n]-a[1],mid; while(l+1<r){ mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid; } printf("%d\n",r); } }

习题7 POJ 3685 Matrix

http://poj.org/problem?id=3685

题解

注意到关于i是单调递增的，可以以此来二分 二分上下限比较有毒…

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<iostream> using namespace std; const int N=50005; #define EPS 1e-6 typedef long long ll; inline ll A(ll i,ll j){ return i*i+100000*i+j*j-100000*j+i*j; } ll n,m; ll place(ll j,ll x){ ll l=0,r=n+1,mid; while(l+1<r){ mid=(l+r)>>1ll; if(A(mid,j)<x) l=mid; else r=mid; } return l; } bool check(ll x){ ll sum=0; for(long long j=1;j<=n;j++){ sum+=place(j,x); } return sum>m-1; } int main() { int t; scanf("%d",&t); while(t--){ scanf("%I64d%I64d",&n,&m); ll l=-100000*n,r=n*n+100000*n+n*n+n*n,mid; check(13); while(l+1<r){ mid=(l+r)>>1ll; if(check(mid)) r=mid; else l=mid; } printf("%I64d\n",l); } }

习题8 POJ 3662 Telephone Lines

题意：给出一个图，每个边有权值，表示连接这条边的费用，现在你要连通1和n,你能免除k条边的费用（这里英文题目巨坑），请问最少费用

题解

二分枚举第k+1长的边 把所有的边大于枚举的为1，其他的为0，跑一遍最短路即可

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=1005; const int M=20005; #define EPS 1e-6 int n,m,k; struct mode{ int u,v,w; }road[M]; bool cmp(mode a,mode b){ return a.w<b.w; } struct node{ int u,v,w,nxt; }edge[M]; int head[N],mcnt; void add_edge(int u,int v,int w){ mcnt++; edge[mcnt].u=u; edge[mcnt].v=v; edge[mcnt].w=w; edge[mcnt].nxt=head[u]; head[u]=mcnt; } int dist[N]; bool vis[N]; struct lode{ int x,y; lode(){} lode(int _x,int _y):x(_x),y(_y){} bool operator <(const lode& a)const{ return x>a.x; } }; priority_queue<lode>q; void Dijkstra(){ memset(dist,0x3f,sizeof dist); memset(vis,0,sizeof vis); while(!q.empty()) q.pop(); dist[1]=0; q.push(lode(0,1)); while(!q.empty()){ int t=q.top().x,u=q.top().y; q.pop(); if(u==n) break; if(t>dist[u]) continue; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].v,w=edge[i].w; if(dist[u]+w<dist[v]){ dist[v]=dist[u]+edge[i].w; q.push(lode(dist[v],v)); } } } } bool check(int x){ memset(head,0,sizeof head); mcnt=0; for(int i=1;i<=m;i++){ add_edge(road[i].u,road[i].v,road[i].w>road[x].w); add_edge(road[i].v,road[i].u,road[i].w>road[x].w); } Dijkstra(); return dist[n]<=k; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d%d%d",&road[i].u,&road[i].v,&road[i].w); sort(road+1,road+m+1,cmp); int l=0,r=m; while(l<r){ int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } if(check(r)) printf("%d\n",road[r].w); else printf("-1\n"); }

习题9 POJ 1759 Garland

http://poj.org/problem?id=1759

题解

推出递推公式

2⋅Hi+2−Hi−1=Hi+1 2 · H i + 2 − H i − 1 = H i + 1 然后二分

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int N=1005; #define EPS 1e-6 double h[N]; int n; bool check(){ if(h[2]<0) return false; for(int i=3;i<=n;i++){ h[i]=2*h[i-1]+2-h[i-2]; if(h[i]<0) return false; } return true; } int main() { double ans=2147483647; scanf("%d%lf",&n,&h[1]); double l=0,r=2147483647,mid; while(r-l>EPS){ mid=(l+r)/2; h[2]=mid; if(check()){ ans=min(ans,h[n]); r=mid; } else l=mid; } printf("%.2lf\n",ans); }

习题10 POJ 3484 Showstopper

这道题的最终问题是：输入恶心 输入数据由空行隔开 可能每个数据间有多个空行… 题意：给出一些等差数列，问哪个数出现了奇数次（保证只有一个，如果不存在，输出no corruption）

题解

由于只有一个，就意味着 如果我们把数字出现次数做前缀和，那么在那个数之前，都是偶数，之后（含）都是奇数，于是可以以此二分

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<iostream> using namespace std; const int N=1000005; #define EPS 1e-6 int X[N],Y[N],Z[N]; char s[N]; int n; long long ans; long long check(long long m){ ans=0; for(int i=1;i<=n;i++){ if(m<X[i]) continue; ans+=min(m-X[i],1ll*Y[i]-X[i])/Z[i]+1; } return ans; } int main() { int f=0,i; while(1){ i=1; while(1){ s[f]=getchar(); if(s[f]=='\n'||s[f]==EOF) break; f++; while((s[f++]=getchar())!='\n') ; sscanf(s,"%d%d%d",&X[i],&Y[i],&Z[i]); //memset(s,0,sizeof s); i++;f=0; } if(s[0]!=EOF) while((s[0]=getchar())=='\n') ; n=i-1; f=1; long long l=0,r=2147483647; long long mid; while(l+1<r){ mid=(l+r)>>1ll; if(check(mid)&1ll) r=mid; else l=mid; } if(check(r)&1) printf("%I64d %I64d\n",r,check(r)-check(r-1)); else printf("no corruption\n"); if(s[0]==EOF) break; } }