Party and Sweets Two Pointers solution

Problems and Contests
#1

Under “two pointers” section of Silver, the problem “Party and Sweets” is listed: https://usaco.guide/silver/2P#problem-cf-1158A. I am not sure of the 2P approach, but as the editorial says, we can use a casework greedy approach. If a_{ij} is the table between the i-th boy and the j-th girl, we need to set all a_{ij} = b_i initially. Assuming \max_b \le \min_g, we should increment \max_b to meet g[j] m-1 times. The remaining g either comes from \max_b or \max 2_b, depending on whether \max_b = \min_g or \max_b < \min_g.

My code (same as editorial's solution) 
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	int max_b = 0, max2_b = 0;
	long long sum_b = 0;
	for(int i=0; i<n; ++i){
		int b; cin >> b;
		if (max_b <= b){
			max2_b = max_b;
			max_b = b;
		} else if(max2_b < b){
			max2_b = b;
		}
		sum_b += b;
	}

	int min_g = 1e8;
	long long sum_g = 0;
	for(int i=0; i<m; ++i){
		int g; cin >> g;
		if(min_g > g){
			min_g = g;
		}
		sum_g += g;
	}

	if(max_b > min_g){
		cout << -1 << endl;
		return 0;
	}
	long long ans = (sum_b - max_b)*m + sum_g; // max_b row = max_b+(g[i]-max_b) = g[i]'s
	if(max_b < min_g){
		ans += max_b - max2_b; // retain one max_b for b[i]=minimum, use diff on max2_b instead
	}
	cout << ans << endl;
	return 0;
}

I understand this greedy, tabular, constructive solution, including why we update \max_b or \max2_b to reach the corresponding girl’s maximum. (I just chose to write these ideas to pen my thoughts down, so I can learn by explaining.)

As I mentioned before, this problem is under “two pointers” section. The Codeforces tags say “two pointers”, “sortings”, and “binary search”. Can you please help me get started with the 2P solution and also the sorting / binary search solutions if they’re related? Thanks for your help!

#2

This problem is not actually two pointers; it’s going to be moved to the Greedy Algorithms with Sorting module soon.

#3

The tags for this problem in Codeforces are “constructive algorithms, greedy, implementation, math” (all corresponding to the tabular greedy solution I mentioned above) and also “binary search, sortings, two pointers”. The tags for this problem in USACO Guide also mention “2P, sorting”. Both these concepts are related (after all, 2P is usually done after sorting the array). So, it seems likely that there is a two pointers solution to Party and Sweets; can you [anyone reading this thread] please guide me towards it?

#4 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    int n, m; cin >> n >> m;
    vector<int> b(n), g(m);
    ll res = 0;
    for(int i=0; i<n; i++){
        cin >> b[i];
        res += b[i];
    }
    for(int i=0; i<m; i++){
        cin >> g[i];
    }
    sort(b.begin(), b.end(), [](int a, int b){
       return a > b; 
    });
    sort(g.begin(), g.end(), [](int a, int b){
       return a > b; 
    });
    res *= m;
    int p1 = 0, p2 = 0, cur = 0;
    int maxB = b[0], minG = g[0];
    for(int i=1; i<n; i++){
        maxB = max(maxB, b[i]);
    }
    for(int i=1; i<m; i++){
        minG = min(minG, g[i]);
    }
    if(maxB > minG){
        cout << -1 << endl;
        return 0;
    }
    while(p2 < m){
        ++cur;
        res += (g[p2] - b[p1]);
        if((cur == m-1 && g[p2+1] != b[p1]) || cur == m){
            cur = 0;
            p1++;
        }
        p2++;
    }
    cout << res << endl;
}