Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Problem link:
- https://www.hackerearth.com/challenges/college/csi-2019/algorithm/c22462cde5b64cf7a353ea0305e89f13/
- is this greedy solution correct ?
- if x < y then always swap and collect zero together (total swap * x + y)
- else just flip all consequitive zero to one (total consequitive zero * y)
- void solve(ll &tc)
- {
- ll n, x, y;
- cin >> n >> x >> y;
- string s;
- cin >> s;
- vector<pair<char, ll>> a;
- for(ll i = 0; i < n; i++) {
- if(a.empty() or a.back().first != s[i]) {
- a.push_back({s[i], 1});
- }
- else {
- a.back().second++;
- }
- }
- ll ans = 0;
- if(x < y) {
- for(ll i = 1; i + 1 < a.size(); i++) {
- if(a[i].first == '1') {
- ans += x;
- }
- }
- ans += y;
- }
- else {
- for(ll i = 0; i < a.size(); i++) {
- if(a[i].first == '0') {
- ans += y;
- }
- }
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment