HakunaMatatata

173

#include <algorithm>
#include <iostream>
#include <map>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;
#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

int main() {
// https://www.acwing.com/solution/content/845/
int n;
cin >> n;
vector<pii> cow(n);
int s, w;
FOR(i, 0, n) {
cin >> s >> w;
cow[i].first = s + w;
cow[i].second = w;
}
sort(cow.begin(), cow.end());
int ans = INT_MIN, sum = 0;
FOR(i, 0, n) {
sum -= cow[i].second;
ans = max(ans, sum);
sum += cow[i].first;
}
cout << ans << endl;
return 0;
}


// 哈夫曼树 每次合并最小2个树，从N->N-1堆之后，具有最优子结构
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;
#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

int main() {
int n, v;
cin >> n;
priority_queue<int, vector<int>, greater<int>> minHeap;
while (n--) {
cin >> v;
minHeap.push(v);
}

int ans = 0;
while (minHeap.size() >= 2) {
int min1 = minHeap.top();minHeap.pop();
int min2 = minHeap.top();minHeap.pop();
int val = min1 + min2;
minHeap.push(val);
ans += val;
}
cout << ans << endl;
return 0;
}


#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;
#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

//  证明参见https://www.acwing.com/solution/content/8130/
int main() {
int n;
cin >> n;
vector<int> arr(n + 1);
FOR(i,1,n+1) cin >> arr[i];
sort(arr.begin()+1,arr.end());
int ans = 0;
FOR(i,1,n+1) ans += abs(arr[i]-arr[(n+1)/2]);
cout << ans << endl;
return 0;
}


#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;

#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

int main() {
int n;
cin >> n;
vector<int> arr(n);
int val;
FOR(i, 0, n) cin >> arr[i];
sort(arr.begin(), arr.end());
partial_sum(arr.begin(), arr.end(), arr.begin());
long ans = 0;
for (int i = 0; i < n - 1; i++) {
ans += arr[i];
}
cout << ans << endl;
}


#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int, int>
using namespace std;
// 题解参考  https://www.acwing.com/solution/content/14773/
// 当时想错的原因是 没读懂题意， 两两不相交的 区间组 的 个数 两两不相交和 组
class Solution {
public:
int rangeGroup(vector<pii> w) {
sort(w.begin(), w.end(),[](pii p, pii q) -> bool { return p.first < q.first; });
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < w.capacity(); i++) {
pii p = w[i];
if (heap.empty() || heap.top() >= p.first) {
heap.push(p.second);
} else {
heap.pop();
heap.push(p.second);
}
}
return heap.size();
}
};
int N;
int main() {
cin >> N;
vector<pii> w;
while (N--) {
int l, r;
cin >> l >> r;
w.push_back({l, r});
}
Solution INSTANCE;
int ans = INSTANCE.rangeGroup(w);
cout << ans;
return 0;
}



#include <algorithm>
#include <iostream>
#include <vector>

#define pii pair<int, int>
using namespace std;

int INF = 0x3F3F3F3F;

class Solution {
public:
int range(vector<pii > data) {
sort(data.begin(), data.end(), [](pii p, pii q) -> bool { return p.second < q.second; });
int ans = 0;
int end = -INF;
const int len = data.size();
for (int i = 0; i < len; i++) {
if (end < data[i].first) {// 小于当前左端点，则更新end位当前区间的右端点
ans++;
end = data[i].second;
}
}
return ans;
}
};

int N;
int l, r;

int main() {
cin >> N;
vector<pii > data;
while (N--) {
cin >> l >> r;
data.push_back({l, r});
}
Solution INSTANCE;
int ans = INSTANCE.range(data);
cout << ans;
return 0;
}


// 按右端点从小到大排序，如果本次end（取右端点）不能包含本次区间，则更新成取本区间的右端点

#include <iostream>
#include <vector>
#include <algorithm>

#define pii pair<int,int>
using namespace std;

bool operator<(pii p1, pii p2) {
return p1.second < p2.second;
}

int INF = 0x3F3F3F3F;

class Solution {
public:
int range(vector<pii > data) {
sort(data.begin(), data.end(), [](pii p, pii q) -> bool { return p.second < q.second; });
int ans = 0;
int end = -INF;
const int len = data.size();
for (int i = 0; i < len; i++) {
if (end < data[i].first) {
ans++;
end = data[i].second;
}
}
return ans;
}
};

int N;
int l, r;

int main() {
cin >> N;
vector<pii > data;
while (N--) {
cin >> l >> r;
data.push_back({l, r});
}
Solution INSTANCE;
int ans = INSTANCE.range(data);
cout << ans;
return 0;
}



#include <iostream>

using namespace std;

class Solution {
public:
int NumberOf1(int n) {
int count = 0;
unsigned int un = n;
while (un) {
count += un & 1;
un = un >> 1; // 高位补0;
}
return count;
}

int NumberOfOne(int n) {
int cnt = 0;
for (int i = 0; i < 32; i++) cnt += (n >> i) & 1;
return cnt;
}
};

int main() {
Solution Instance;
cout << Instance.NumberOf1(-2) << endl;
cout << Instance.NumberOfOne(-2) << endl;
return 0;
}



// 最小公倍数*最大公约数 = 两数之积

#include <vector>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
if (a % b == 0)return b;
else return gcd(b, a % b);
}

int lcm(int a, int b) {
return (a * b / gcd(a, b));
}
// 最小公倍数*最大公约数 = 两数之积
int main() {
int a, b;
cin >> a >> b;
cout << lcm(27,15) << endl;
}



#include <vector>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
if (a % b == 0)return b;
else return gcd(b, a % b);
}

int lcm(int a, int b) {
return (a * b / gcd(a, b));
}
// 最小公倍数*最大公约数 = 两数之积
int main() {
int a, b;
cin >> a >> b;
cout << lcm(a,b) << endl;
}