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;
}华华给月月准备礼物
二分答案即可，要注意不能取到0code
#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;
}
京公网安备 11010502036488号