Posted in Greedy

CF 545C Woodcutters

7/14/2017
Problem: http://codeforces.com/contest/545/problem/C
Solution: For trees from left to right, if it can be cut to left then cut left,
or cut right if possible. Otherwise, just leave it there. The
reasoning is simple. If one tree is cut left, then it has no affect on
following trees at all, so we would try to cut left as long as it’s
possible. The worst consequence of cutting a tree right would be that
the next tree wouldn’t be cut, which does not change the overall
result at all.
Note: Pay special attention to the overflow for x[i] – p.


#include<iostream>
using namespace std;
int x[100005] = {0};
int h[100005] = {0}; 

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> h[i];
	}
	int p = INT_MIN;
	int cnt = 0;
	x[n + 1] = INT_MAX;
	for (int i = 1; i <= n; i++) {
		if (h[i] < (long long)x[i] - p) {
			p = x[i];
			cnt ++;
			// cout << i << "L" << endl; 
		} else if (h[i] < x[i + 1] - x[i]) {
			p = x[i] + h[i];
			cnt ++; 
			// cout << i << "R" << endl;
		}
		p = max(p, x[i]); 
	}
	cout << cnt;
	return 0; 
}

Posted in Greedy

CF 372A Counting Kangaroos is Fun

7/12/2017
Problem: http://codeforces.com/problemset/problem/372/A
Solution: Divide the sorted array in the middle, and then apply greedy to match
pairs.


#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	int a[500005] = {0};
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int ans = n;
	int p1 = 1, p2 = n / 2 + 1;
	while (p1 <= n /2 && p2 <= n) {
		if (a[p1] * 2 <= a[p2] ) {
			p1 ++;
		}
		p2 ++;
	}
	cout << n - p1 + 1;
	return 0;
}