练习

A

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n, t, count = 0;
    vector<int> v;
    cin >> n;
    while (n--) {
  cin >> t;
  if (t % 2) {
      v.push_back(t);
  }
    }
    sort(v.begin(), v.end());
    n = v.size();
    for (int i = 0; i < n; i++) {
  cout << v[i];
  if (i != n - 1) cout << ',';
    }
    return 0;
}

B

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef struct NODE {
    string name;
    double time;
}node;
int cmp(node a, node b) {
    return a.time < b.time;
}
int main() {
    vector<node> v;
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
  node t;
  cin >> t.name;
  cin >> t.time;
  v.push_back(t);
    }
    sort(v.begin(), v.end(),cmp);
    cout << v[k - 1].name;
    return 0;
}

C

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n,0);
    for (int i = 0; i < n; i++) {
  cin >> a[i];
    }
    long long count = 0;
    for (int i = 0; i < n-1; i++) {
  for (int j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
    swap(a[j], a[j + 1]);
    count++;
      }
  }
    }
    cout << count;
    return 0;
}

D

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
    map<int, int> m;
    int m_value = 0, n,t;
    cin >> n;
    for (int i = 0; i < n; i++) {
  cin >> t;
  m[t]++;
    }
    map<int, int>::iterator i;
    for (i = m.begin(); i != m.end(); i++) {
  if (i->second > m_value) m_value = i->second;
    }
    for (i = m.begin(); i != m.end(); i++) {
  if (i->second == m_value) {
      cout << i->first;
      break;
  }
    }
    return 0;
}

E

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;
    int n, t;
    cin >> n;
    while (n--) {
  cin >> t;
  s.insert(t);
    }
    cout << s.size() << endl;
    set<int, int>::iterator i = s.begin();
    for (; i != s.end(); i++) {
  cout << *i << ' ';
    }
    return 0;
}

F

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef struct NODE {
    string sex;
    double height = 0;
}node;
int cmp(node a, node b) {
    if (a.sex == "male" && b.sex == "male") return a.height < b.height;
    else if (a.sex == "female" && b.sex == "female") return a.height > b.height;
    else {
  if (a.sex == "male") return 1;
  else return 0;
    }
}
int main() {
    vector<node> v;
    node t;
    int n;
    cin >> n;
    while (n--) {
  cin >> t.sex >> t.height;
  v.push_back(t);
    }
    sort(v.begin(), v.end(),cmp);
    int len = v.size();
    for (int i = 0; i < len; i++) {
  printf("%.2lf ", v[i].height);
    }
    return 0;
}

G快速排序掌握基础以及提升

#include <iostream>
using namespace std;
int L[100005];
void QSort(int L[], int left, int right)  //快速排序
{
    if (left >= right)    return;    //条出循环
    int temp = L[left];    //采用最左边的数作为支点
    int    i = left, j = right;
    while (i < j)
    {
  while (i < j && L[j] >= temp)  j--;
  L[i] = L[j];    //将比支点小的数移到低端
  while (i < j && L[i] <= temp)    i++;
  L[j] = L[i];    //将比支点大的数移到高端
    }
    L[i] = temp;    //支点移到i位置上**易错点**
    QSort(L, left, i - 1);    //递归处理左边的数
    QSort(L, i + 1, right);    //递归处理右边的数
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
  cin >> L[i];
    QSort(L, 0, n - 1);
    for (int i = 0; i < n; i++)
  cout << L[i] << ' ';
    return 0;
}

H - 线段覆盖（贪心与排序）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct NODE {
    int s;
    int t;
}node;
int cmp(node a, node b) {
    if (a.s == b.s) return a.t < b.t;
    else return a.s < b.s;
}
int main() {
    vector<node> v(107);
    int end = 0, int_s, int_t, n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> int_s >> int_t;
        v[i].s = int_s;
        v[i].t = int_t;
    }
    sort(v.begin(), v.begin() + n, cmp);
    /*贪心算法*/
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (v[i].s >= end) {
            ans++;
            end = v[i].t;
        }
    }
    cout << ans;
    return 0;
}

I - 奖学金(重载结构体运算符与sort)

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3e2 + 1;
struct NODE{
    int Chinese = 0;
    int Math = 0;
    int English = 0;
    int id;
    int operator>(const NODE b) {
        int total_a = Chinese + Math + English;
        int total_b = b.Chinese + b.Math + b.English;
        if (total_a > total_b) {
            return 1;
        }
        else if (total_a == total_b && Chinese > b.Chinese) {
            return 1;
        }
        else if (total_a == total_b && Chinese == b.Chinese && id < b.id) {
            return 1;
        }
        else return 0;
    }
}stu[MAXN];
int cmp(struct NODE a, struct NODE b) {
    return a > b;
}
int main() {
    int n, a, b, c;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b >> c;
        stu[i].Chinese = a;
        stu[i].Math = b;
        stu[i].English = c;
        stu[i].id = i;
    }
    sort(stu + 1, stu + n + 1,cmp);
    for (int i = 1; i <= 5; i++) {
        cout << stu[i].id << ' ' << stu[i].Chinese + stu[i].Math + stu[i].English << endl;
    }
    return 0;
}

J - 配对

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 1;
int array_a[MAXN];
int array_b[MAXN];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> array_a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> array_b[i];
    }
    sort(array_a, array_a + n);
    sort(array_b, array_b + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(array_a[i] - array_b[i]);
    }
    cout << ans;
    return 0;
}

K - 奶牛图书馆（greater()）

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2e4 + 1;
int a[MAXN];
int main() {
    int n, h;
    cin >> n >> h;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n, greater<int>());
    int ans = 0,total = 0;
    for (int i = 0; i < n; i++) {
        total += a[i];
        ans++;
        if (total >= h) break;
    }
    cout << ans;
    return 0;
}

L - 逆排序（递归排序/线段树）

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e2 + 1;
int ans = 0;
vector<int> v1(MAXN);
vector<int> v2(MAXN);
void msort(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    msort(l, mid);
    msort(mid + 1, r);
    int i = l;
    int j = mid + 1;
    int k = l;
    while (i <= mid && j <= r) {
        if (v1[i] <= v1[j]) v2[k++] = v1[i++];
        else {
            ans += mid - i + 1;
            v2[k++] = v1[j++];
        }
    }
    while (i <= mid) v2[k++] = v1[i++];
    while (j <= r) v2[k++] = v1[j++];
    for (int i = l; i <= r; i++) v1[i] = v2[i];
}
int main() {
    int n, t;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        v1[i] = t;
    }
    msort(1, n);
    cout << ans;
    return 0;
}

M - 排队接水

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAXN = 2e3 + 1;
double sum = 0.0;
int n = 0;
struct NODE {
    double time;
    int pos;
}man[MAXN];
int cmp(struct NODE a, struct NODE b) { return a.time < b.time; }
double acc(int i) {
    if (i == 1) return 0.0;
    else return acc(i - 1) + man[i-1].time;
}
int main() {
    double t;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        man[i].time = t;
        man[i].pos = i;
    }
    sort(man + 1, man + 1 + n,cmp);
    for (int i = 1; i <= n; i++) {
        cout << man[i].pos << ' ';
        sum += acc(i);
    }
    cout << endl;
    cout << fixed << setprecision(2) << sum / n * 1.0;
    return 0;
}

• 累计求sum的方法不如解答中的好，用个屁的递归