几道有趣的贪心题

贪心题"/>

几道有趣的贪心题

思路:

首先,对于两个人a,b我们判断要抢A给B还是抢B给A,假设前面的策略比较好m(a)-p(b)>=m(b)-p(a),即m(a)+p(a)>=m(b)+p(b).于是我们先按照m+p从大到小排序.注意到答案有单调性,二分抢的人数k,

然后我们可以先选好最小的k个m+p的p,其余的n-k选出最大的m,然后调整,从n-k个中调整被资助的人.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f
#define writen(x) write(x),printf("\n")
using namespace std;
const int N = 2e6 + 10;
int n;
struct rec {int a, b;bool operator <(const rec& i) const {return a + b > i.a + i.b;}
}a[N];
bool check(int x) {priority_queue<PII> hrob, hgive;vector<char> vis(n + 1, 0);for (int i = 1; i <= n - x; ++i) hrob.emplace(a[i].a, i);int sa = 0, sb = 0 ;for (int i = 1; i <= x; ++i) {sa += hrob.top().first;vis[hrob.top().second] = 1;hrob.pop();}for (int i = n - x + 1; i <= n; ++i) hgive.emplace(a[i].b, i), sb += a[i].b;if (sa >= sb) return true;priority_queue<PII> heap;for (int i = 1; i <= n - x; ++i) if (!vis[i]) heap.emplace(a[i].a, i);for (int i = n - x; i >= x + 1; --i) {int tt = hgive.top().first;if (a[i].b < tt) {sb -= tt, sb += a[i].b;hgive.pop(); hgive.emplace(a[i].b, i);}if (vis[i]) {sa -= a[i].a;auto t = heap.top(); heap.pop();while (t.second >= i) {t = heap.top(); heap.pop();}vis[t.second] = 1, vis[i] = 0;sa += t.first;}if (sa >= sb) return true;}return false;
}
signed main() {IOS;cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i].a;for (int i = 1; i <= n; ++i) cin >> a[i].b;sort(a + 1, a + 1 + n);int l = 0, r = n / 2;while (l < r) {int mid = (l + r + 1) >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << l << "\n";
}

思路:

首先我们得特判:如果A!=A+AB+BA,或者B!=B+AB+BA(数量),那么肯定无解.

接下来我们有个显然的贪心,选出尽可能多的双字符,即ab和ba

我们可以将字符串分成若干个子串,每个子串相邻字符都不同:

即ababab...

1.如果abababa或babababa为偶数,那么全部变成ab和ba是最好的

2.如果abababa.为奇数,先存下来,调整

然后我们先在尽可能保证cntab>=ab的前提下分配给cntba,然后再对bababa去掉头/尾然后转化一部分给ab,有可能cntab比较多,可以用同样办法给cntba.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f
#define writen(x) write(x),printf("\n")
using namespace std;
bool cmp(int a, int b) {return a > b;
}
void solve() {string s;int A, B, AB, BA, cntAB = 0, cntBA = 0;vector<int> ab, ba, odd;cin >> A >> B >> AB >> BA >> s;s = "?" + s;if (count(all(s), 'A') != A + AB + BA || count(all(s), 'B') != B + BA + AB) return cout << "NO\n", void(0);int n = s.size() - 1;for (int i = 1; i <= n; ++i) {int j = i;while (j + 1 <= n && s[j] != s[j + 1]) ++j;int len = j - i + 1;if (len % 2 == 0) {if (s[i] == 'A') cntAB += len / 2, ab.emplace_back(len / 2);else cntBA += len / 2, ba.emplace_back(len / 2);}else {odd.emplace_back(len / 2);}i = j;}//在尽可能满足cntAB>=AB的前提下,使得cntAB尽量大for (int x : odd) {int t = min(max(0ll, AB - cntAB), x);cntAB += t;cntBA += x - t;}sort(all(ab), cmp);sort(all(ba), cmp);//在cntBA>=BA的前提下,把多余的BA分给ABfor (int x : ba) {if (cntBA > BA) {--cntBA, --x;int t = min(cntBA - BA, x);cntBA -= t;cntAB += t;}}//在cntAB>=AB的前提下,把多余的AB分给BAfor (int x : ab) {if (cntAB > AB) {--cntAB, --x;int t = min(cntAB - AB, x);cntAB -= t;cntBA += t;}}cout << ((cntAB >= AB && cntBA >= BA) ? "YES" : "NO") << "\n"; 
}
signed main() {IOS;int T;cin >> T;while (T--) solve();
}