一、
解题思路：主要还是写出val / m，按这个排序，就行了
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;struct doro {int m, val;double cmp;
} arr[105];bool cmp(const doro& a, const doro& b) {return a.cmp > b.cmp;
}int main() {int n;double T;cin >> n >> T;for (int i = 0; i < n; i++) {cin >> arr[i].m >> arr[i].val;arr[i].cmp = (double)arr[i].val / arr[i].m;}sort(arr, arr + n, cmp);double ans = 0.0;for (int i = 0; i < n; i++) {if (T <= 0) break;if (T >= arr[i].m) {ans += arr[i].val;T -= arr[i].m;}else {ans += arr[i].cmp * T;T = 0;}}printf("%.2f\n", ans);return 0;
}二、
解题思路：排序，然后逆序相乘累加再除总个数就行了
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;struct doro{int val, pos;
}arr[1005];bool cmp(const doro& a, const doro& b) {return a.val < b.val;
}
int main() {int n; cin >> n;for (int i = 1; i <= n; i++) {cin >> arr[i].val;arr[i].pos = i;}sort(arr + 1, arr + 1 + n, cmp);double ans = 0;for (int i = 1; i < n; i++) {ans += arr[i].val * (n - i);cout << arr[i].pos << " ";}cout << arr[n].pos << endl;printf("%.2f", ans / n);return 0;
}三、
解题思路：贪心，总数要参加更多的活动，给一个pair<int,int>或者结构体表示u和v按结束时间排序，然后就是贪心比较就行了
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;struct line {int s, e;
}arr[1000010];bool cmp(const line& a, const line& b) {if (a.e == b.e)return a.s < b.s;return a.e < b.e;
}int main() {int n; cin >> n;for (int i = 1; i <= n; i++) {cin >> arr[i].s >> arr[i].e;}sort(arr + 1, arr + 1 + n, cmp);int ans = 0;int cur_end = -1;for (int i = 1; i <= n; i++) {if (arr[i].s >= cur_end) {ans++;cur_end = arr[i].e;}}cout << ans;return 0;
}四、
解题思路：俩个写法，一个用multiset<int>,或者优先队列
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {int n; cin >> n;priority_queue<int, vector<int>, greater<int>>pq;for (int i = 1; i <= n; i++) {int temp; cin >> temp;pq.push(temp);}int ans = 0;for (int i = 1; i < n; i++) {int a = pq.top();pq.pop();int b = pq.top();pq.pop();ans += a + b;pq.push(a + b);}cout << ans;return 0;
}#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {multiset<int>tt;int n; cin >> n;for (int i = 1; i <= n; i++) {int temp; cin >> temp;tt.insert(temp);}int ans = 0;for (int i = 1; i < n; i++) {auto a = tt.begin();int frist = *a;tt.erase(tt.begin());auto b = tt.begin();int scenod = *b;tt.erase(tt.begin());ans += (frist + scenod);tt.insert(frist + scenod);}cout << ans;return 0;
}
五、
解题思路：模拟从头到尾的过程，贪心使得当俩者相加大于x时，使得第二个盒子的糖果减少，如果不够减少，则为0
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {int n, x; cin >> n >> x;vector<int>arr(n + 1);for (int i = 1; i <= n; i++)cin >> arr[i];ll ans = 0;for (int i = 1; i < n; i++) {if (arr[i] + arr[i + 1] > x) {int chi = arr[i] + arr[i + 1] - x;ans += chi;if (arr[i + 1] >= chi)arr[i + 1] -= chi;elsearr[i + 1] = 0;}}cout << ans;return 0;
}六、
解题思路：就这个题来说，仔细思考会发现从开始到结尾都是单调递增的，所以可以用单调栈为维持这个单调性
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;string f(string s, int k) {stack<char> st;for (char c : s) {while (!st.empty() && k > 0 && st.top() > c) {st.pop(); k--;}st.push(c);}while (k > 0 && !st.empty()) {st.pop();k--;}string res;while (!st.empty()) {res += st.top();st.pop();}reverse(res.begin(), res.end());int i = 0;while (i < res.size() && res[i] == '0') i++;res = res.substr(i);return res.empty() ? "0" : res;
}int main() {string s; cin >> s;int k; cin >> k;cout << f(s, k) << endl;return 0;
}七、
解题思路：模拟+贪心，我就摘力气最小的，所以按照力气排序即可
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int n, s, chiar, hand;
struct node {int h, q;
}arr[5005];bool cmp(const node& a, const node& b) {if (a.q == b.q)return a.h < b.h;return a.q < b.q;
}int main() {cin >> n >> s;cin >> chiar >> hand;for (int i = 1; i <= n; i++) {cin >> arr[i].h >> arr[i].q;}sort(arr + 1, arr + 1 + n, cmp);int ans = 0;for (int i = 1; i <= n; i++) {if (chiar + hand >= arr[i].h && s >= arr[i].q) {ans++; s -= arr[i].q;}}cout << ans;return 0;
}STL大法好
八、
解题思路：queue加map
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {int n, m; cin >> n >> m;int ans = 0;map<int, int>tt;queue<int>qu;for (int i = 1; i <= m; i++) {int temp; cin >> temp;if (!tt.count(temp)) {qu.push(temp);tt[temp]++;ans++;}if (tt.size() > n) {int front = qu.front();qu.pop();tt.erase(front);}}cout << ans;return 0;
}九、
解题思路：set+lower_bound解题
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {int n; cin >> n;set<int>tt;int temp; cin >> temp;ll ans = temp; tt.insert(temp);for (int i = 2; i <= n; i++) {cin >> temp;auto num = tt.lower_bound(temp);if (num != tt.end() && num != tt.begin()) ans += abs(temp - *num) > abs(temp - *prev(num)) ? abs(temp - *prev(num)) : abs(temp - *num);else if (num == tt.begin())ans += abs(temp - *num);elseans += abs(temp - *prev(num));tt.insert(temp);}cout << ans;return 0;
}
