#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
int n;
pair <int,int> cow[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int w,s;
        scanf("%d%d",&w,&s);
        cow[i] = {w + s,w};
    }
    sort(cow,cow + n);
    int res = -2e9,sum = 0;
    for(int i = 0;i < n;i ++){
        int w = cow[i].second,s = cow[i].first - w;
        res = max(res,sum - s);
        sum += w;
    }
    printf("%d\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
    sort(a,a + n);
    int res = 0;
    for(int i = 0;i < n;i ++) res += abs(a[i] - a[n / 2]);
    printf("%d\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int t[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++) scanf("%d",&t[i]);
    sort(t,t + n);
    long long res = 0;
    for(int i = 0;i < n;i ++) res += t[i] * (n - i - 1);
    printf("%lld\n",res);
    return 0;
}

数据结构 堆 $heap$

堆的简介

堆($Heap$)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆分为两个板块，一个是大根堆，一个是小根堆。

• 大根堆

  每一个节点元素的值都不小于左右子树的值
  根节点的元素最大

• 小根堆

  每一个节点元素的值都不大于左右子树的值
  根节点的元素最小

堆的实现

手写堆

在写呢

#include <iostream>
#include <queue>
using namespace std;
const int N = 10010;
int n;
priority_queue <int,vector <int>,greater <int> > heap;
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int x;
        scanf("%d",&x);
        heap.push(x);
    }
    int res = 0;
    while(heap.size() > 1){
        int x = heap.top();
        heap.pop();
        int y = heap.top();
        heap.pop();
        res += x + y;
        heap.push(x + y);
    }
    printf("%d\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w) const {
        return l < w.l;
    }
}range[N];
int main(){
    int s,t;
    scanf("%d%d",&s,&t);
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    bool success = false;
    int res = 0;
    for(int i = 0;i < n;i ++){
        int j = i,r = -2e9;
        while(range[j].l <= s && j < n){
            r = max(range[j].r,r);
            j ++;
        }
        if(r < s){
            res = -1;
            break;
        }
        res ++;
        if(r >= t){
            success = true;
            break;
        }
        s = r;
        i = j - 1;
    }
    if(!success) res = -1;
    printf("%d\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w) const{
        return l < w.l;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    priority_queue <int,vector <int>,greater <int> > heap;
    for(int i = 0;i < n;i ++){
        Range r = range[i];
        if(heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else{
            heap.pop();
            heap.push(r.r);
        }
    }
    printf("%d\n",heap.size());
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w) const{
        return r < w.r;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    int res = 0,ed = -2e9;
    for(int i = 0;i < n;i ++){
        if(ed < range[i].l){
            res ++;
            ed = range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w)const{
        return r < w.r;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    int res = 0,ed = -2e9;
    for(int i = 0;i < n;i ++){
        if(ed < range[i].l){
            res ++;
            ed = range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}

题目描述

blablabla

样例

blablabla

算法1

(并查集) $O(10000)$

首先看题目，我们找到了这一句话：

现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

找到某个人的最早的祖先，找祖先的这种问题，用并查集就能很好的实现，那下面我们来看看怎么实现。

手写这道题目输入的是人的名字，那为了更好的找到这个人的祖先并输出他的姓名，我们可以用一个$unordered\underline{~}map$来做映射。然后就直接手写并查集啦。

时间复杂度

并查集的每一个操作都是近乎$O(1)$的，一共有$10000$组父子关系，那就大概是$O(10000)$这个神奇的复杂度。

参考文献

C++ 代码

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map <string,string> p; // 每个节点的父节点，用unordered_map做映射
string find(string x){ // 查找根节点操作，因为父节点存的都是string类型的，所以定义为string类型
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin.tie(0); // 优化一下cin，cout
    cout.tie(0);
    char op; // 每个操作的类型
    string father; // 因为题目是输入一个父亲，然后跟着一些儿子，所以就需要拿一个字符串记下当前这个人的父亲，记得不要在while循环里定义哦，因为每个父亲不一定只有1个儿子
    while(cin>>op,op != '$'){ // 循环，只要op为$，就跳出循环
        string name; // 当前这个人的名字
        cin>>name;
        if(op == '#'){ // 如果这是个父亲
            father = name; // 找到一个父亲，存下来，方便后面儿子找到父亲
            if(p[name] == "") p[name] = name; // 如果这个人没有父亲，就把自己设为祖宗
        }
        else if(op == '+') p[name] = father; // 如果是个儿子，把自己的父亲找到，并赋值
        else cout<<name<<" "<<find(name)<<endl; // 否则就是查找这个人的祖宗，题目要求输出这个人的名字和他的祖宗的名字
    }
    return 0;
}