Posted in Binary Search, Uncategorized

PKU 3 Monthly Expense

Problem: http://acmicpc.openjudge.cn/practice/003/?lang=en_US


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

// 3 1
// 10 10 10

int main() {
	int n, m;
	int max = 0;
	long long sum = 0;
	cin >> n >> m;
	for (int i = 1; i <= n ; i++) {
		cin >> a[i];
		if (a[i] > max) {
			max = a[i];
		}
		sum += a[i];
	}
	int l = max, r = sum;
	while (l < r) {
		// cout << l << ' ' << r << endl; 
		int mid = l + (r - l) / 2;
		long long temp = 0;
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			temp += a[i];
			if (temp > mid) {
				cnt ++;
				temp = a[i];
			} else if (temp == mid) {
				cnt ++;
				temp = 0;
			}
		}
		if (temp != 0) {
			cnt ++;
		}
		// cout << cnt << endl;
		if (cnt > m) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	cout << l;
	return 0;
}

Posted in Binary Search

PKU 2 Pie

Problem: http://acmicpc.openjudge.cn/practice/002/


#include<iostream>
#include<iomanip>
#include<cmath>
const double pi = acos(-1.0);
using namespace std;
double a[100005] = {0};
int n, f;

bool check(double mid) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		cnt += a[i] / mid;
	}
	return cnt >= f;
}

int main() {
	cin >> n >> f;
	f++; 
	int tmp = 0;
	double max = 0;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		a[i] = pi * tmp * tmp;
		if (a[i] > max) {
			max = a[i];
		}
	}
	double l = 0, r = max;
	while (r - l >= 1e-5) {
		double mid = l + (r - l) / 2.0;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	printf("%.3f", l);
	return 0;
}

Posted in Binary Search

PKU 1 Aggressive Cows

Problem: http://acmicpc.openjudge.cn/practice/001/


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

int main() {
	ios::sync_with_stdio(false);
	int n, c;
	cin >> n >> c;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int l = 1, r = a[n];
	while (l + 1 < r) {
		// cout << l << ' ' << r << ' '; 
		int m = l + (r - l) / 2;
		a[0] = - m - 1;
		int cnt = 0;
		long long temp = 0;
		for (int i = 1; i <= n; i++) {
			temp += a[i] - a[i - 1];
			if (temp >= m) {
				cnt ++;
				temp = 0;
			}
		}
		// cout << cnt << endl;
		if (cnt >= c) {
			l = m;
		} else {
			r = m;
		}
	} 
	cout << l;
	return 0;
} 

Posted in Binary Search

CF 812C

6/28/2017
Problem: http://codeforces.com/problemset/problem/812/C
Solution: Binary Search. At first I misunderstood the statement, the “xj” thing. For each mid, a sort must be applied.


#include<iostream>
#include<algorithm>
using namespace std;
long long temp [100005] = {0};

int main() {
	int n, s;
	cin >> n >> s;
	int a[100005] = {0};
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int l = 0, r = n + 1;
	long long sum = 0;
	while (l + 1 < r) {
		sum = 0;
		long long mid = (l + r) / 2;
		for (int i = 1; i <= n; i++) {
			temp[i] = a[i] + mid * i;
		}
		sort(temp + 1, temp + n + 1);
		sum = 0;
		for (int i = 1; i <= mid; i++) {
			sum += temp[i];
		}
		if (sum <= s) {
			l = mid;
		} else {
			r = mid;
		}
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		temp[i] = a[i] + l * i;
	}
	sort(temp + 1, temp + n + 1);
	for (int i = 1; i <= l; i++) {
		ans += temp[i];
	}
	cout << l << ' ' << ans;
	return 0;
}

Posted in Binary Search

CF 778A String Game

7/12/2017
Problem: http://codeforces.com/problemset/problem/778/A
Solution: Binary search on time.

 
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[200005] = {0};
bool b[200005];

int main() {
	string s1, s2;
	cin >> s1 >> s2;
	int len = s1.length();
	for (int i = 1; i <= len; i++) {
		cin >> a[i];
	}
	int l = 0, r = len + 1;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		memset(b, false, sizeof(b));
//		for (int i = 1; i <= 7; i++) {
//			b[i] = false;
//		}
		for (int i = 1; i <= mid; i++) {
			b[a[i]] = true;
		}
		string s = "";
		for (int i = 1; i <= len; i++) {
			if (!b[i]) {
				s += s1[i - 1];
			}
		}
		// cout << l << ' ' << r << ' ' << s << endl;
		int p = s.length() - 1;
		int p2 = s2.length() - 1;
		while (p >= 0 && p2 >= 0) {
			if (s[p] == s2[p2]) {
				p2 --;
			}
			p--;
		}
		if (p2 >= 0) {
			r = mid;
		} else {
			l = mid;
		}
	}
	cout << l;
	return 0;
}