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

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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
06-23 18:33
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 18:22
点赞 评论 收藏
分享
05-23 21:27
成都信息工程大学 网络安全
避坑
避坑恶心到我了大家好，今天我想跟大家聊聊我在成都千子成智能科技有限公司（以下简称千子成）的求职经历，希望能给大家一些参考。千子成的母公司是“同创主悦”，主要经营各种产品，比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司？没错，就是那种类型的公司。我当时刚毕业，急需一份临时工作，所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元，还包住宿，这吸引了我。面试的时候，HR也说了同样的话，感觉挺靠谱的。于是，我满怀期待地等待结果。结果出来后，我通过了面试，第二天就收到了试岗通知。试岗的内容就是地推销售，公司划定一个区域，然后你就得见人就问，问店铺、问路人，一直问到他们有意向为止。如果他们有兴趣，你就得摇同事帮忙推动，促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床，收拾后去公司，然后唱歌跳舞（销售公司都这样），7:55早课（类似宣誓），8:05同事间联系销售话术，8:15分享销售技巧，8:30经理训话。9:20左右从公司下市场，公交、地铁、自行车自费。到了市场大概10点左右，开始地推工作。中午吃饭时间大约是12:00，公司附近的路边盖饭面馆店自费AA，吃饭时间大约40分钟左右。吃完饭后继续地推工作，没有所谓的固定中午午休时间。下午6点下班后返回公司，不能直接下班，需要与同事交流话术，经理讲话洗脑。正常情况下9点下班。整个上班的一天中，早上到公司就是站着的，到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位，百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波，公司的投入成本几乎只有租金和工资，没有中央空调。早上2小时，晚上加班2小时，纯蒸桑拿。没有任何福利，节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思：新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数，类似传销模式，把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方，不能依墙而坐。早上吃早饭在公司外面的安全通道，未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候，带你的师傅会给你营造一个钱多事少离家近的工作氛围，吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之，大家在找工作的时候一定要擦亮眼睛，避免踩坑！———来自网友
qq乃乃好喝到咩噗茶：不要做没有专业门槛的工作
点赞 评论 收藏
分享
05-19 16:43
广西师范大学 Java
点赞 评论 收藏
分享
06-23 22:49
湖南农业大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 26届校招投递进展 #
11692次浏览 122人参与
# 考公VS就业，你怎么选？ #
62318次浏览 424人参与
# 我的职场心眼子段位 #
24401次浏览 601人参与
# 24届的你们现状如何了？ #
75904次浏览 444人参与
# 职场捅娄子大赛 #
403777次浏览 4024人参与
# 你秋招想去哪些公司 #
12696次浏览 637人参与
# 产品薪资爆料 #
115655次浏览 826人参与
# 参加完秋招的机械人，还参加春招吗？ #
51764次浏览 556人参与
# 设计人如何选offer #
115490次浏览 724人参与
# 分享一个让你热爱工作的瞬间 #
29260次浏览 315人参与
# 为了找工作你花了哪些钱？ #
21263次浏览 215人参与
# 你都遇到过哪些离谱的求职经历 #
12882次浏览 41人参与
# 第一份工作能做外包吗？ #
20966次浏览 245人参与
# 听劝，这个简历怎么改 #
175394次浏览 1134人参与
# 一人推荐一个机械人值得去的公司 #
406525次浏览 4145人参与
# 第一份工作应该选择高薪还是大平台 #
138477次浏览 835人参与
# 入职第四天，心情怎么样 #
28829次浏览 414人参与
# 机械人你觉得今年行情怎么样？ #
777次浏览 18人参与
# 工作中的卑微时刻 #
16210次浏览 132人参与
# 应届生进小公司有什么影响吗 #
76016次浏览 1025人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务