寒鸽儿のBlog

View

1. CF1379B (#657Div2B)
2. CF1379C (#657Div2C)

detail

CF1379B (#657Div2B)

思路

枚举a , 贪心求 $|b-c|$ 的两个最小值(分别在$b - c \geqslant 0$ 和 $b - c \leqslant 0$ )时。然后看能否构造符合的解。
$\mathcal{O(r)}$

code

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define itra std::vector<int>::iterator;
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
inline void ponchline() { cout << "##################################" << endl; }
inline ll qp(ll a, ll b, ll p) { ll res = 1%p; for(;b;b>>=1) { if(b&1)res=res*a%p; a=a*a%p; } return res; }
inline ll gcd(ll a, ll b) { while(b) { int t = b; b = a%b; a=t; } return a; }
mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;}
 
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
 
//vector< VI > edge;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin>>tests;
	while(tests--) {
		ll l, r, m;
		cin >> l >> r >> m;
		for(ll a = r; a >= l; --a) {
			ll t = m % a;
			if(t <= r - l && m / a != 0) {
				cout << a << ' ' << l + t << ' ' << l << endl;
				break;
			}
			if((m / a + 1) * a - m <= r - l) {
				cout << a << ' ' << r - ((m / a + 1) * a - m) << ' ' << r << endl;
				break;	
			}
 		}
	}
	return 0;
}
 

CF1379C (#657Div2C)

思路

b可以选择无限种 , 至多只能选一种的b。
枚举选择的b , 贪心求选哪些a。
$\mathcal{O(n)}$

事项

注意二分的边界情况 , pls = 0可能是一个都不能选(建议下标从1开始并给0设置一个边界值以区分) , 要特判。

code

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define itra std::vector<int>::iterator;
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

inline void ponchline() { cout << "##################################" << endl; }
inline ll qp(ll a, ll b, ll p) { ll res = 1%p; for(;b;b>>=1) { if(b&1)res=res*a%p; a=a*a%p; } return res; }
inline ll gcd(ll a, ll b) { while(b) { int t = b; b = a%b; a=t; } return a; }
mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;}

const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 123456;

//vector< VI > edge;

struct pr {
	int x, y;
	pr() {}	
	pr(int x, int y) : x(x), y(y) {}
} prs[maxn];

ll sum[maxn];

int getpls(int l, int r, int key) {
	while(l < r) {
		int mid = (l + r + 1) >> 1;
		if(prs[mid].x >= key) l = mid;
		else r = mid - 1;
	}
	return l;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin>>tests;
	while(tests--) {
		int n, m, nn;
		cin >> n >> m;
		nn = n;
		for(int i = 0; i < m; ++i) cin >> prs[i].x >> prs[i].y;
		sort(prs, prs + m, [&](pr x, pr y){return x.x > y.x || x.x == y.x && x.y > y.y;});
		sum[0] = prs[0].x;
		for(int i = 1; i < m; ++i) sum[i] = sum[i-1] + prs[i].x;
		ll ans = sum[min(m-1, n-1)], tt;
		for(int i = 0; i < m; ++i) {
			tt = 0;
			int pls = getpls(0, m - 1, prs[i].y);
			if(prs[pls].x < prs[i].y) pls = -1;
			if(pls + 1 >= n) ans = max(ans, sum[n - 1]);
			else {
				if(~pls) {
					tt += sum[pls];
					n -= pls + 1;
				}
				if(i > pls) --n, tt += prs[i].x;
				tt += 1ll * n * prs[i].y;
				ans = max(ans, tt);
			}
			n = nn;
		}
		cout << ans << endl;
	}
	return 0;
}