A. Points in Segments
给n个，1～m的子集，求1～n中所有没在这些子集中出现过的数字
把子集区间合并为集合s，输出1～n中没有在s中出现过的数
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
int n, m;
vector<PII> segs;
vector<bool> mark(110);
void merge() {
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first) {
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
void solve() {
merge();
for(auto [i, j] : segs) {
// cout << i << ' ' << j << endl;
for(int pos = i; pos <= j; pos ++) {
mark[pos] = true;
}
}
int cnt = 0;
for(int i = 1; i <= m; i++) {
if(!mark[i]) cnt ++;
}
cout << cnt << endl;
if(cnt == 0) {
return;
}
for(int i = 1; i <= m; i++) {
if(!mark[i]) cout << i << " ";
}
}
signed main() {
cin >> n >> m;
while(n--) {
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
solve();
}
~B. Obtaining the String
给定两个长度相等的字符串，通过每次交换相邻两个字符的操作，把第一个字符串调整为第二个字符串，问最少的操作数和每次操作所交换元素的第一个元素的下标
第一次读错题以为字符串中没有相同的字母，所以这么做了：把第二个字符串的字母，映射成它的下标，则第一个字符串就可以转换为一个数字串，冒泡排序即可
#include "bits/stdc++.h"
using namespace std;
vector<int> arr(100);
vector<int> ans;
int cnt;
void bubbleSort(vector<int> &arr, int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素位置
cnt++;
ans.push_back(j + 1);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
return;
}
}
}
signed main(){
int n;
string s1, s2;
cin >> n;
cin >> s1 >> s2;
map<char, int> mp;
for(int i = 0; i < n; i++) mp[s2[i]] = i;
for(int i = 0; i < n; i++) {
if (mp.find(s1[i]) == mp.end()) {
// 如果 s1[i] 不在 s2 中出现
cout << -1;
return 0;
}
arr[i] = (mp[s1[i]]);
}
bubbleSort(arr, n);
cout << cnt << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
}
如果有相同的字符则不能这么映射了，因为后一个字符会把前一个相同的字符的映射给覆盖掉，所以把mp.first的类型改成queue来维护相同字母的序号即可
#include "bits/stdc++.h"
using namespace std;
vector<int> arr(100);
vector<int> ans;
int cnt;
void bubbleSort(vector<int> &arr, int n) {
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素位置
cnt++;
ans.push_back(j + 1);
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
return;
}
}
}
signed main(){
int n;
string s1, s2;
cin >> n;
cin >> s1 >> s2;
//判断是否可以排序成一样的，只要判断两个字符串中每个字母的个数是否分别相等即可
int ok[30] = {0};
for(int i = 0;i < n;i++) {
ok[s1[i] - 96]++;
ok[s2[i] - 96]--;
}
for(int i = 1;i <= 26;i++) {
if(ok[i] != 0) {
cout<<-1;
return 0;
}
}
map<char, queue<int>> mp;
for(int i = 0; i < n; i++) mp[s2[i]].push(i);
for(int i = 0; i < n; i++) {
// if (mp.find(s1[i]) == mp.end()) {
// // 如果 s1[i] 不在 s2 中出现
// cout << -1;
// return 0;
// }//由于可能存在多个相同的字母，例如，s2中有两个a，而s1中只有一个，这么写检测不出来
arr[i] = mp[s1[i]].front();
mp[s1[i]].pop();
}
bubbleSort(arr, n);
cout << cnt << endl;
for(int i : ans) cout << i << ' ';
cout << endl;
}
*C. Songs Compression
Ivan有n首歌,第i首歌原始大小为ai,压缩后为bi。他有一个容量为m的U盘。
他想把所有歌复制到U盘中,可以选择任意歌曲压缩,使得总大小不超过m。
求最少需要压缩的歌曲数,如果无法完成则输出-1。
#include<bits/stdc++.h>
using namespace std;
#define int long long
// 定义长长整型便于处理大数
int n, m, t1, t2;
// n:歌曲数 m:U盘容量
// t1:所有歌曲压缩后大小总和 t2:所有歌曲原始大小总和
vector<pair<int, int>> t;
// t数组存储每首歌的(原始大小,压缩后大小)
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first - a.second > b.first - b.second;
}
// cmp函数用于排序,按压缩效果从大到小排序
signed main() {
cin >> n >> m;
t.resize(n);
for(int i = 0; i < n; i++){
cin >> t[i].first >> t[i].second;
t1 += t[i].second;
t2 += t[i].first;
}
// 读入输入,计算t1和t2
if(t1 > m){
cout << -1;
return 0;
}
// 判断压缩后是否能装下,不能则输出-1
sort(t.begin(), t.end(), cmp);
// 排序
for(int i = 0; i < n; i++){
if(t2 <= m) {
cout << i;
return 0;
}
t2 -= t[i].first - t[i].second;
}
// 贪心算法,从效果最大的开始压缩,直到容量满足
cout << n;
return 0;
}