hello.cpp - Opengist

q2.cpp · 1.6 KiB · C++ Raw

1	#include <iostream>
2	#include <vector>
3	#include <algorithm>
4	#include <climits>
5	#include <bits/stdc++.h>
6	using namespace std;
7	#define ll long long
8	# updated
9	ll minCostProduct(const vector<vector<ll>> &seg)
10	{
11	int n = seg.size();
12
13	// Sort by starting endpoint (L)
14	vector<vector<ll>> sortedL = seg;
15	sort(sortedL.begin(), sortedL.end(), [](const vector<ll> &a, const vector<ll> &b)
16	{
17	if (a[0] != b[0])
18	return a[0] < b[0];
19	return a[1] < b[1]; });
20
21	// Sort by ending endpoint (R)
22	vector<vector<ll>> sortedR = seg;
23	sort(sortedR.begin(), sortedR.end(), [](const vector<ll> &a, const vector<ll> &b)
24	{
25	if (a[1] != b[1])
26	return a[1] < b[1];
27	return a[0] < b[0]; });
28
29	ll minCost = LLONG_MAX; // Minimum cost of valid non-overlapping segments
30	ll minProd = LLONG_MAX; // Minimum product of costs for valid pairs
31
32	int r = 0;
33
34	// Iterate over sortedL (by left endpoint)
35	for (const auto &cur : sortedL)
36	{
37	// Check for valid non-overlapping segments (sortedR's R < cur.L)
38	while (r < n && sortedR[r][1] < cur[0])
39	{
40	minCost = min(minCost, sortedR[r][2]); // sortedR[r][2] is the cost
41	++r;
42	}
43
44	// Calculate the product of costs if a valid segment is found
45	if (minCost != LLONG_MAX)
46	{
47	ll prod = minCost * cur[2];
48	minProd = min(minProd, prod);
49	}
50	}
51
52	// Return the result
53	return (minProd != LLONG_MAX) ? minProd : -1; // Return -1 if no valid pair is found
54	}

q2_last.cpp · 724 B · C++ Raw

1	int findMinPairingCost(const vector<Segment>& segments) {
2	int minCost = INT_MAX;
3	int n = segments.size();
4
5	if (n < 2) return -1;
6
7	vector<Segment> sortedSegments = segments;
8	sort(sortedSegments.begin(), sortedSegments.end(), [](const Segment& a, const Segment& b) {
9	return a.R < b.R \|\| (a.R == b.R && a.L < b.L);
10	});
11
12	int minSingleCost = INT_MAX;
13
14	for (int i = 0; i < n; i++) {
15	for (int j = 0; j < i; j++) {
16	if (sortedSegments[j].R < sortedSegments[i].L) {
17	int pairCost = sortedSegments[i].cost * sortedSegments[j].cost;
18	minCost = min(minCost, pairCost);
19	}
20	}
21	}
22
23	return minCost == INT_MAX ? -1 : minCost;
24	}

q3.cpp · 298 B · C++ Raw

1	int minMoves(vector<int>arr, int n, int k) {
2
3	sort(arr.begin(), arr.end());
4
5	int i = 0, j = n - 1;
6	int moves = 0;
7
8	while (i <= j) {
9
10	if (arr[i] + arr[j] <= k) {
11	i++;
12	}
13
14	j--;
15
16	moves++;
17	}
18
19	return moves;
20	}