双重二分,wa了一下午,实在不太明白为啥一写二分就会进入死循环.
INF要设的大一些,本题设0x3f3f3f3f会wa.
本题有负数, 二分时(l+r)/2与(l+r)>>1的结果有所不同;
如 l=0,r=-1,则 (l+r)/2=0,而(l+r)>>1=-1,而我们需要的正确答案是-1,所以第一种二分必须写成(l+r)>>1
以下两种二分可过:
(l+r)>>1
/* * FillName: 二重二分 * Created: 2016年04月02日 14时48分41秒 星期六 * Author: Akrusher * */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d ",(x)) #define out2(x1,x2) printf("%d %d ",(x1),(x2)) #define outf(x) printf("%f ",(x)) #define outlf(x) printf("%lf ",(x)) #define outlf2(x1,x2) printf("%lf %lf ",(x1),(x2)); #define outll(x) printf("%I64d ",(x)) #define outlld(x) printf("%lld ",(x)) #define outc(str) printf("%c ",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const ll INF=1e12; //INF要设的大一些,本题设0x3f3f3f3f会wa const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true; int t,n; ll m; ll cal(ll i,ll j){ //返回矩阵a[i][j]的值,数组会超内存 return i*i+j*j+100000*i-100000*j+i*j; //int可能会爆 } ll C(ll x){ //此处改为int会莫名奇妙的wa,返回值也得是ll int l,r,mid2; ll cnt; //此处一定要是ll cnt=0; rep(j,1,n+1){ l=1,r=n+1; while(r>l){ mid2=(r+l)/2; if(cal(mid2,j)>=x) r=mid2; //本题要求的是第m大的值 else l=mid2+1; } cnt+=r-1; } return cnt; } int main() { ll ub,lb,mid; in(t); while(t--){ in(n); inlld(m); lb=-INF,ub=INF; //INF要设的大一些 while(ub>lb){ mid=(ub+lb)>>1; //有负数,不能写成(l+r)/2 if(C(mid)>=m) ub=mid; //类似中位数的那个题 else lb=mid+1; } outlld(ub-1);//最后要减1 } return 0; }
下面这种也可以过
(l+r)/2
/* * FillName: 二重二分 * Created: 2016年04月02日 14时48分41秒 星期六 * Author: Akrusher * */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d ",(x)) #define out2(x1,x2) printf("%d %d ",(x1),(x2)) #define outf(x) printf("%f ",(x)) #define outlf(x) printf("%lf ",(x)) #define outlf2(x1,x2) printf("%lf %lf ",(x1),(x2)); #define outll(x) printf("%I64d ",(x)) #define outlld(x) printf("%lld ",(x)) #define outc(str) printf("%c ",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const ll INF=1e12; //INF要设的大一些,本题设0x3f3f3f3f会wa const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true; int t,n; ll m; ll cal(ll i,ll j){ //返回矩阵a[i][j]的值,数组会超内存 return i*i+j*j+100000*i-100000*j+i*j; //int可能会爆 } ll C(ll x){ //此处改为int会莫名奇妙的wa,返回值也得是ll int l,r,mid2; ll cnt; //此处一定要是ll cnt=0; rep(j,1,n+1){ l=1,r=n+1; while(r>l){ mid2=(r+l)/2; if(cal(mid2,j)>=x) r=mid2; //本题要求的是第m大的值 else l=mid2+1; } cnt+=r-1; } return cnt; } int main() { ll ub,lb,mid; in(t); while(t--){ in(n); inlld(m); lb=-INF,ub=INF; //INF要设的大一些 while(ub-lb>1){ mid=(ub+lb)/2; if(C(mid)>=m) ub=mid; else lb=mid; } outlld(lb); } return 0; }
下面这种做标记的二分也挺有意思
/* * FillName: 二重二分 * Created: 2016年04月02日 14时48分41秒 星期六 * Author: Akrusher * */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d ",(x)) #define out2(x1,x2) printf("%d %d ",(x1),(x2)) #define outf(x) printf("%f ",(x)) #define outlf(x) printf("%lf ",(x)) #define outlf2(x1,x2) printf("%lf %lf ",(x1),(x2)); #define outll(x) printf("%I64d ",(x)) #define outlld(x) printf("%lld ",(x)) #define outc(str) printf("%c ",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const ll INF=1e12; //INF要设的大一些,本题设0x3f3f3f3f会wa const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true; int t,n; ll m; ll cal(ll i,ll j){ //返回矩阵a[i][j]的值,数组会超内存 return i*i+j*j+100000*i-100000*j+i*j; //int可能会爆 } ll C(ll x){ //此处改为int会莫名奇妙的wa,返回值也得是ll ll l,r,mid2; ll cnt,res; //此处一定要是ll cnt=0; rep(j,1,n+1){ l=1,r=n; res=0; while(r>=l){ mid2=(r+l)>>1;//起标记的作用 if(cal(mid2,j)<=x) { res=mid2; l=mid2+1; } else r=mid2-1; } cnt+=res; } return cnt; } int main() { ll ub,lb,mid,ans; in(t); while(t--){ in(n); inll(m); lb=-INF,ub=INF; //INF要设的大一些 ans=0; while(ub>=lb){ mid=(ub+lb)>>1; //有负数,不能写成(l+r)/2 if(C(mid)>=m) { ans=mid; ub=mid-1; //带标记的二分 } else lb=mid+1; } outll(ans); } return 0; }