牛客算法竞赛入门课第三节习题

K-th Number

直接二分答案，然后判断答案是否符合要求即可。。。。

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

ll t , n , k , m;
ll a[N];

bool check(ll x){
    ll num = 0 , s = 0;
    for(int i = 1 , j = 1 ; j <= n ; ++j){
        if(a[j] >= x) num++;  //大于x的值的个数
        if(num == k){    //出现k个值大于等于x
            s += n - j + 1;  //将有边界大于等于j的区间都算上
            while(a[i] < x){ 
                s += n - j + 1;  //左边界右移 如果num没少 又加一次右边界等于大于j的区间
                i++;   //这个左边界值大于等于x
            }
            num--;
            i++;
        }
    }
    return s >= m;
}

int main(void){
    scanf("%lld" , &t);
    while(t--){
        scanf("%lld%lld%lld" , &n , &k , &m);
        for(int i = 1 ; i <= n ; ++i) scanf("%lld" , &a[i]);
        ll l = 1 ,  r = 1e9 , ans = 0 , mid;
        while(l <= r){
            mid = (l + r)>>1;
            if(check(mid)) ans = mid , l = mid + 1;
            else r = mid - 1;
        }
        printf("%lld\n" , ans);
    }
    return 0;
}

位数差

分治，将问题转换为，[0,n)这个区间假设我们存在一个分治函数，可以求到[0,mid),[mid,n)，之间的答案，那么最终的答案就还要加上a[i]在左边，a[j]在右边即可！

于是我们就只要匹配右边进位的个数然后二分查找即可

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int a[N];
int b[9] = { 10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };

ll solve(int l , int r){
    if(r - l == 1) return 0;
    int mid = (l + r) >> 1;
    ll ans = solve(l , mid) + solve(mid , r);
    sort(a + mid , a +  r);
    for(int i = l ; i < mid ; ++i){
        for(int j = 0 ; j < 9 ; ++j){
            if(b[j] - a[i] > 0)
                ans += a + r - lower_bound(a + mid , a + r , b[j] - a[i]);

        }
    }
    return ans;
}

int main(void){
    int n = read();
    for(int i = 0 ; i < n ; ++i)
        a[i] = read();
    printf("%lld\n" , solve(0 , n));
    return 0;
}

栗酱的不等式

直接二分答案！冲，因为x最小是2，所以n要从8开始

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int main(void){
    ll n;
    while(cin>>n){
        ll ans = -1 , l = 8 , r = 1e16 , mid;
        ll cnt , x;
        while(l <= r){
            mid = (l + r) >> 1;
            for(cnt = 0 , x = 2 ; x * x * x <= mid ; ++x){
                cnt += mid / (x * x * x);
            }
            if(cnt > n)     r = mid - 1;
            else if(cnt == n) ans = mid , r = mid - 1;
            else l = mid + 1; 
        }
        cout<<ans<<endl;
    }
    return 0;
}

完全平方数

因为完全平方数开根号之后就是一段连续的数字，所以可以直接对两个端点开根号然后剪一下就可以了

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int main(void){
    int T = read();
    while(T--){
        int l = read() , r = read();
        cout << floor(sqrt(1.0 * r)) - ceil(sqrt(1.0 * l)) + 1 << endl;
    }
    return 0;
}

wyh的物品

二分答案 ， 没有难点

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int n , m;

struct node{
    double a , b , c;
    bool operator < (const node& b) const{
        return c > b.c;
    }
}a[N];

bool check(double x){
    for(int i = 1 ; i <= n ; ++i) {
        a[i].c = a[i].b - x * a[i].a;
    }
    sort(a + 1 , a + 1 + n);
    double ans = 0;
    for(int  i = 1 ; i <= m ; ++i)
        ans += a[i].c;
    return ans > eps;
}



int main(void){
    int T = read();
    while(T--){
        n = read() , m = read();
        for(int i = 1 ; i <= n ; ++i){
            a[i].a = read();
            a[i].b = read();
        }
        double l = eps , r = 1e9 , mid ;
        for(int i = 1 ; i <= 100 ; ++i){
            mid = (r + l) / 2.0;
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%.2lf\n" , mid);
    }
    return 0;
}

聪明的质监员

二分+前缀和

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
ll n , m , s;
int w[N] , v[N];
int l[N] , r[N];
ll sum[N] , cnt[N];

ll calc(ll x){
    for(int i = 1 ; i <= n ; ++i){
        if(w[i] >= x){
            sum[i] = sum[i - 1] + v[i];
            cnt[i] = cnt[i - 1] + 1;
        }
        else{
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }
    }
    ll sm = 0;
    for(int i = 1; i <= m ; ++i){
        sm += (cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
    }
    return sm;
}

int main(void){
    n = read() , m = read() , s = read();
    for(int i = 1 ; i <= n ; ++i)
        w[i] = read() , v[i] = read();
    for(int i = 1 ; i <= m ; ++i)
        l[i] = read() , r[i] = read();
    int reft  = 0 , right = INF;
    while(reft <= right){
        int mid = (reft + right) >> 1;
        if(calc(mid) >= s) reft = mid + 1;
        else right = mid - 1;
    }  
    cout<<min(abs(calc(right) - s) , abs(calc(right + 1) - s))<<endl;
    return 0;
}

[CQOI2010]扑克牌

只要能想到二分答案这个题目就很简单了

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
int n , m;
int a[55];

bool check(ll x){
    ll num = 0 ;
    for(int i = 1 ; i <= n ; ++i){
        if(a[i] < x) num += (x - a[i]);
    }
    return num <= m && num <=x;
}
int main(void){
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        a[i] = read();
    ll l = 0 , r = 2e9 , mid;
    while(l + 1 < r){
        mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid ;
    }
    cout<<l<<endl;
    return 0;
}

[SCOI2010]传送带

这个题目我们很容易就能想到在ab和cd上的某个点的时候，值有最大，过了和未达到都是小于，所以很明显是一个三分，只是在三分的时候要三分两次，及对ab三分和对cd三分，想明白了之后就很简单了，就是一个套两次三分的题目

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e7 + 7;
const int INF = 0x3f3f3f3f;

const double eps = 1e-4;
double p , q , r;

struct node{
    double x , y;
}a , b , c ,d , e , f;

double dis(node a , node b){
    return sqrt(eps + (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double check1(double x){
    f = { c.x + (x / dis(c,d) * (d.x - c.x)),c.y + (x / dis(c,d) * (d.y - c.y)) };
    return dis(e , f) / r + (dis(c , d) -  x) / q;
}

double check(double x){
    e = { a.x + x / dis(a , b) * (b.x - a.x) , a.y + x / dis(a ,b) * (b.y - a.y)};
    double l = 0 , r = dis(c , d);
    for(int i = 1 ; i <= 1000 ; ++i){
        double lm = l + (r - l) / 3 , rm = r - (r - l) / 3;
        if(check1(lm) >= check1(rm)) l = lm;
        else r = rm;
    }
    return check1(l) + x / p;
}

int main(){
    cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
    cin>>p>>q>>r;
    double l = 0 , r = dis(a , b);
    for(int i = 1 ; i <= 1000 ; ++i){
        double lm = l + (r - l) / 3 , rm = r - (r - l) / 3;
        if(check(lm) >= check(rm)) l = lm;
        else r = rm;
    } 
    printf("%.2f\n" , check(l));
    return 0;
}

[SHOI2017]期末考试

因为收到两个方程的约束，所以就是一个抛物线，三分最高点就好了

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ull read() { ull s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int INF = 0x3f3f3f3f;

const int N = 1e6 + 7;
ull a , b , c;
ull n , m ;
ull t[N] , g[N];

ull check(ull x){
    ll p = 0 , q = 0 , res = 0;
    for(int i = 1 ; i <= m ; ++i){
        if(g[i] >= x) p += g[i] - x;
        else q += x - g[i];
    }
    if(b <= a) res = p * b;
    else{
        if(q >= p) res = p * a;
        else res = q * a + (p - q) * b;
    }
    for(int i = 1 ; i <= n ; ++i)
        if(t[i] < x) res += (x - t[i]) * c;
    return res;
}

int main(void){
    a = read() , b = read() , c = read();
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        t[i] = read();
    for(int i = 1 ; i <= m ; ++i)
        g[i] = read();
    ull l = 1 , r = *max_element(g + 1 , g + m + 1);   
    while( l + 10 < r){
        ull m = l + r >>1 , mm = (m + l) >> 1;
        if(check(m) >= check(mm)) r = m;
        else l = mm;
    } 
    ull ans = 2e18;
    for(ll i = l ; i <= r ; ++i) ans = min(ans , check(i));
    cout<<ans<<endl;
    return 0;
}

华华给月月准备礼物

二分答案即可，要注意不能取到0

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ull read() { ull s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll a[N];
int n , k;

bool check(ll x){
    ll cnt = 0 ;
    for(ll i = 1 ; i <= n ; ++i){
        cnt += a[i] / x;
    }
    return cnt >= k;
}

int main(void){
    cin>>n>>k;
    for(int i = 1 ; i <= n ; ++i){
        cin>>a[i];
    }
    ll l = 0 , r = 1e9 + 7;
    while(l < r){
        ll mid = (r + l + 1 ) >> 1;
        if(check(mid)) l = mid;
        else r = mid  - 1;
    }
    cout<<l<<endl;
    return 0;

}

Chocolate Eating

这个题目以前好像做过，不是用二分做的，要做的话也不难，首先二分答案，然后在二分的过程中标记每一巧克力吃的时间，

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

ll l , r , mid , ans ;
ll n , d , a[N] , day[N];

bool check(ll x){
    ll tot = 0 , sum = 0;
    for(int i = 1 ; i <= d ; ++i){
        sum = sum >> 1;
        while(sum < x){
            sum += a[++tot];
            if(tot > n) return false;
            if(x && x == ans) day[tot] = i;
        } 
    }
    return true;
}

int main(void){
    n = read() , d = read();
    for(int i = 1 ; i <= n ; ++i){
        a[i] = read() , r += a[i];
    }
    while( l <= r ){
        mid = (l + r) >> 1;
        if(check(mid)) ans = mid , l = mid + 1;
        else r = mid - 1;
    }
    printf("%lld\n" , ans );
    check(ans);`q
    for(int i = 1 ; i <= n ; ++i){
        if(day[i]) printf("%lld\n" , day[i]);
        else printf("%lld\n" , d);
    }
    return 0;
}

4 Values whose Sum is 0

最暴力的做法就是写一个四重循环然后去爆搜他，但是很明显是不行的，所以我们考虑更优的做法，我们可以算出三重循环的和，然后去二分第四重，但是这个还是不够用的，所以我们要考虑更优的做法

既然可以二分一重那么我就可以考虑二分两重，要二分两重就要考虑一些特殊的做法，比如我把两个的值加起来，形成一个新的数组，然后我们就只需要循环两重，然后二分这个新的数组去找就可以了.

还有就是我像一个憨憨一样拿着c++交了两发java，看到头文件报错还以为是poj。。

code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e6 + 7;

int a[N] , b[N] , c[N] , d[N];

vector<int> v;

int main(void){
    int n = read();
    for(int i = 1 ; i <= n ; ++i){
        a[i] = read();
        b[i] = read();
        c[i] = read();
        d[i] = read();
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            v.push_back(a[i] + b[j]);
        }
    }
    sort(v.begin() , v.end());
    ll ans = 0;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            int x = -(c[i] + d[j]);
            ans += upper_bound(v.begin() , v.end() , x) - lower_bound(v.begin() , v.end() , x);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Drying

题目都读不懂。。。简直吐了，还有输入和输出的样例也是有毒，那个sample input #1和sample input #2是不用理的，输入和输出都不用理，然后那个还会卡一波cin选手，然后这个题目也就不难了，很容易就能看出来直接二分

code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
ll a[N] , n , k;

bool check(ll x){
    ll ans = 0;
    for(int i = 1 ; i <= n; ++i){
        if(a[i] > x) ans += (a[i] - x + k - 2) / (k - 1);
    }
    return ans <= x;
}

int main(void){
    ll max ; 
    while(scanf("%lld" , &n)!=EOF){
        for(int i = 1 ; i <= n ; ++i){
            scanf("%lld" , &a[i]);
        }
        ll l = 1 , r = 1e9;
        scanf("%lld" , &k);
        if(k == 1){
            printf("%lld\n" , *max_element(a + 1 , a + 1 + n));
            continue;
        }
        while(l < r){
            ll mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1 ;
        }
        printf("%lld\n" , l);
    }
    return 0;
}

Monthly Expense

题目的意思就是有n个数把他们分成m组，每一组求和，然后问m组最大的数字最小是多少

就是一个简单的二分题

code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;

int n , m;
int a[N];

bool check(ll x){
    ll tmp = 0 , res = 1;
    for(int i = 1 ; i <= n ;++i){
        if(a[i] > x) return 0;
        if(tmp + a[i] > x){
            tmp = 0;
            res++;
        } 
        tmp += a[i];
    }
    return res <= m ;
}

int main(void){
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        a[i] = read();
    ll l = 0 , r = 1e9 ,ans;
    while(l <= r){
        int mid = (l + r) >>1;
        if(check(mid)) r = mid - 1 , ans = mid;
        else l = mid + 1; 
    }
    printf("%lld\n" , ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 23:16
点赞 评论 收藏
分享
11-29 15:05
浙江大学 机械工程师
点赞 评论 收藏
分享
11-12 21:11
浙江横店影视职业学院 运营
点赞 评论 收藏
分享
12-01 15:27
已编辑
中南大学 Java
请教各位大牛子几个问题
1.为什么都在追求核心部门？除了稳定以外，核心部门还有什么优势吗？比如晋升快什么的或年终发的多什么的？2.北京的公积金不买房都能取出来吗？好取吗？只能用于租房吗？3.如果部门里大部分人职级很高那校招生进去就会晋升很快是这么个道理吗？4.10&nbsp;9&nbsp;5&nbsp;周五6点下班的工作作息在互联网算是中等还是略微加班还是加班较严重呢？5.电网是非要研究生学历才能进去吗？本科有机会吗？6.北京、上海、深圳三地工作幸福指数何如？都买不起房的情况下
汉献帝刘协：公积金随便提的吧，我这里一年可以全提出来一次，不用离职，不用交什么证明，北京不至于那么恶心你
牛客创作赏金赛 牛客在线求职答疑中心
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 25届秋招总结 #
446421次浏览 4560人参与
# 春招别灰心，我们一人来一句鼓励 #
43097次浏览 544人参与
# 地方国企笔面经互助 #
8115次浏览 18人参与
# 同bg的你秋招战况如何？ #
78960次浏览 579人参与
# 实习必须要去大厂吗？ #
55976次浏览 962人参与
# 虾皮求职进展汇总 #
118731次浏览 901人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
12031次浏览 306人参与
# 实习，投递多份简历没人回复怎么办 #
2456697次浏览 34872人参与
# 提前批简历挂麻了怎么办 #
150185次浏览 1980人参与
# 在找工作求抱抱 #
906781次浏览 9425人参与
# 如果公司给你放一天假，你会怎么度过？ #
4803次浏览 57人参与
# 你投递的公司有几家约面了？ #
33243次浏览 188人参与
# 投递实习岗位前的准备 #
1196700次浏览 18553人参与
# 机械人春招想让哪家公司来捞你？ #
157724次浏览 2267人参与
# 双非本科求职如何逆袭 #
663054次浏览 7397人参与
# 发工资后，你做的第一件事是什么 #
13036次浏览 62人参与
# 工作中，努力重要还是选择重要？ #
36390次浏览 387人参与
# 简历中的项目经历要怎么写？ #
87083次浏览 1517人参与
# 参加完秋招的机械人，还参加春招吗？ #
20223次浏览 240人参与
# 我的上岸简历长这样 #
452315次浏览 8091人参与
牛客网
牛客企业服务