fractional-knapsack.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n; double c; cin >> n >> c;
	//         weight, value
	vector<pair<int, int>> v;
	double ans = 0;

	while (n--) {
		int a, b; cin >> a >> b;
		v.push_back({a, b});
	}

	sort(v.begin(), v.end(), [](pair<int, int> &a, pair<int, int> &b) {
		return (1.0 * a.second / a.first) > (1.0 * b.second / b.first);
	});

	for (auto d : v) {
		if (d.first <= c) {
			c -= d.first;
			ans += d.second;
		} else {
			ans += (1.0 * d.second / d.first) * c;
			break;
		}
	}
	
	cout << ans << endl;

	return 0;
}

huffman.cpp

#include <bits/stdc++.h>
using namespace std;

struct Node {
	char c;
	Node *left, *right;

	Node(char ch) {
		c = ch;
		left = right = NULL;
	}
};

struct Comperator {
	bool operator()(pair<int, Node*> &a, pair<int, Node*> &b) {
		return a.first > b.first;
	}
};

void show(Node *root, string s) {
	if (!root) return;

	if (root->left == NULL && root->right == NULL) {
		cout << root->c << " : " << s << endl;
	}

	show(root->left, s + "0");
	show(root->right, s + "1");
}

int main() {
	string s; cin >> s; 
	vector<int> freq(26, 0); 
	for (auto c : s) freq[c - 'a']++;

	priority_queue<pair<int, Node*>, vector<pair<int, Node*>>, Comperator> pq;
	for (int i = 0; i < 26; i++) {
		if (freq[i] != 0) {
			pq.push({freq[i], new Node((char)(i + 'a'))});
		}
	}

	while (pq.size() > 1) {
		auto a = pq.top(); pq.pop();
		auto b = pq.top(); pq.pop();

		Node* parent = new Node('#');
		parent->left = a.second;
		parent->right = b.second;

		pq.push({(a.first + b.first), parent});
	}

	show(pq.top().second, "");

	return 0;
}