猫史档案馆

题目描述：

地图计算

有一n*n地图，每个点的权值等于i*i+100000*i+j*j-100000*j+i*j

求第k大的权值

解析：这题数据很大，直接喵存，然后sort，绝对爆掉。

          怎么办呢？

          说白了就是二分套二分

//地图计算：有一n*n地图，每个点的权值等于i*i+100000*i+j*j-100000*j+i*j.求第k大的权值
#include<iostream>
#include<cstdio>
using namespace std;
const long long K=1e5;
long long n,k;
long long check2(long long i,long long j){//计算i，j的快乐值
    return i*i+K*i+j*j-K*j+i*j;           //j*(i+j-K)+i*i+K*i;可以看到i不变，j增大，值递减（因为i<=50000,j<=50000)
}
//返回比num大的数的个数
long long check1(long long hang,long long num){
    long long L=1,R=n;
    while(L<=R){
        long long mid=(L+R)/2;
        if (check2(hang,mid)>=num) L=mid+1;
        else R=mid-1;
    }
    return R;//返回在第i行比num大的数的个数
}
bool check(long long num){//返回比num大的数的个数
    long long ans=0;
    for (long long i=1;i<=n;i++){//分行计算
        ans+=check1(i,num);      //记录比num大的数的个数
        if (ans>=k) return 1;    //比num大的数大于等于K个，返回
    }
    return 0;                    //比num大的数小于K个，返回0
}
int main(){
    scanf("%lld%lld",&n,&k);
    long long L=-1e10,R=1e10;
    while (L<=R){//二分查找第K大的数
        long long mid=(L+R)/2;
        if (check(mid)) L=mid+1;
        else R=mid-1;
    }
    printf("%lld\n",R);
    return 0;
}

这里有：

第一个二分

    while (L<=R){//二分查找第K大的数
        long long mid=(L+R)/2;
        if (check(mid)) L=mid+1;
        else R=mid-1;
    }

第二个二分

    while(L<=R){
        long long mid=(L+R)/2;
        if (check2(hang,mid)>=num)L=mid+1;
        else R=mid-1;
    }

标准程序如下：

#include<iostream>
#include<cstdio>
using namespace std;
const long long K=1e5;
long long n,k;
long long check2(long long i,long long j){
    return i*i+K*i+j*j-K*j+i*j;
}
long long check1(long long hang,long long num){
    long long L=1,R=n;
    while(L<=R){
        long long mid=(L+R)/2;
        if (check2(hang,mid)>=num) L=mid+1;
        else R=mid-1;
    }
    return R;
}
bool check(long long num){
    long long ans=0;
    for (long long i=1;i<=n;i++){
        ans+=check1(i,num);
        if (ans>=k) return 1;
    }
    return 0;
}
int main(){
    scanf("%lld%lld",&n,&k);
    long long L=-1e10,R=1e10;
    while (L<=R){
        long long mid=(L+R)/2;
        if (check(mid)) L=mid+1;
        else R=mid-1;
    }
    printf("%lld\n",R);
    return 0;
}