#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
int a[N];
int main(){
    int n;

    cin>>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]);
    cout<<res;

    return 0;
}

#include<iostream>

using namespace std;

const int N = 3010;
int f[N][N];
int a[N],b[N];
int n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    for(int i=1;i<=n;i++){
        int maxv=1;
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]) f[i][j]=max(f[i][j],maxv);
            if(a[i]>b[j]) maxv=max(maxv,f[i-1][j]+1);//这里没有必要每次单独开一层循环求f[i-1][j]的最长上升子序列,反正每次f[i][j]用的都是前一层的
            //那么直接在大循环中求即可

        }
    }

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res;

    return 0;
}

双指针

class Solution {
public:
    int cnt[257];//使用数组的话明显会快！
    int lengthOfLongestSubstring(string s) {
        int ans=0;
        for(int i=0,j=0;i<s.size();i++){
            while(j<=i&&cnt[s[i]]>=1) cnt[s[j++]]--;
            cnt[s[i]]++;
            ans=max(i-j+1,ans);
        }
        return ans;
    }
};

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct Player
{
    int arrive_time, play_time;
    int start_time, waiting_time;

    bool operator<(const Player &p1)const//sort排序
    {
        if (start_time != p1.start_time) return start_time < p1.start_time;
        return arrive_time < p1.arrive_time;
    }

    bool operator>(const Player &p1)const//优先队列中比较大小
    {
        return arrive_time > p1.arrive_time;
    }

};

struct Table
{
    int id;
    int fin_time;

    bool operator>(const Table &t1)const//优先队列中比较大小
    {
        if (fin_time != t1.fin_time) return fin_time > t1.fin_time;
        return id > t1.id;
    }
};

priority_queue<Player, vector<Player>, greater<Player>> normal_player, vip_player;
priority_queue<Table, vector<Table>, greater<Table>> normal_table, vip_table;

const int N = 110, INF = 0x3f3f3f3f;
bool is_vip[N];
int serve_cnt[N];

vector<Player> player;


int dateToInt(int hh, int mm, int ss) {
    return hh * 3600 + mm * 60 + ss;
}

void printDate(int t) {
    printf("%02d:%02d:%02d", t / 3600, t % 3600 / 60, t % 60);
}

void assign(priority_queue<Player, vector<Player>, greater<Player>>& ps,
    priority_queue<Table, vector<Table>, greater<Table>>& ts) {
    auto p = ps.top(); ps.pop();
    auto t = ts.top(); ts.pop();

    int wait_time = t.fin_time - p.arrive_time;

    p.start_time = t.fin_time;
    p.waiting_time = round(wait_time / 60.0);
    serve_cnt[t.id]++;
    player.push_back(p);
    ts.push({ t.id,t.fin_time + p.play_time });
}

int main() {
    int n;
    cin >> n;
    //避免在下面top或者pop的时候还要额外的做出判断，这里插入一个不可能取到的值
    vip_player.push({ INF }); normal_player.push({ INF });

    while (n--)
    {
        int hh, mm, ss, p, tag;
        scanf("%d:%d:%d %d %d", &hh, &mm, &ss, &p, &tag);
        p = min(p, 120);
        p *= 60;
        int t = dateToInt(hh, mm, ss);
        if (tag == 1) vip_player.push({ t,p });
        else normal_player.push({ t,p });
    }

    int k, m;
    cin >> k >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        is_vip[x] = true;
    }
    //避免在下面top或者pop的时候还要额外的做出判断，这里插入一个不可能取到的值
    normal_table.push({ -1,INF }); vip_table.push({ -1,INF });
    for (int i = 1; i <= k; i++) {
        if (is_vip[i]) vip_table.push({ i,8 * 3600 });
        else normal_table.push({ i,8 * 3600 });
    }


    while (normal_player.size() > 1 || vip_player.size() > 1)
    {
        auto np = normal_player.top();//普通玩家
        auto vp = vip_player.top();//vip玩家
        int arrive_time = min(np.arrive_time, vp.arrive_time);

        //把普通球台和vip球台到达的时间都设置为优先到达的玩家时间，这样一直让玩家维持在队列中的形态，
        //由于设置的是最先到达的玩家，所以不用担心这样算起来玩家的等待时间会有问题，因为其他玩家还没到呢，是不能算等待
        //时间的。
        while (normal_table.top().fin_time < arrive_time)
        {
            auto t = normal_table.top();
            normal_table.pop();
            t.fin_time = arrive_time;
            normal_table.push(t);
        }
        while (vip_table.top().fin_time < arrive_time)
        {
            auto t = vip_table.top();
            vip_table.pop();
            t.fin_time = arrive_time;
            vip_table.push(t);
        }

        auto nt = normal_table.top();
        auto vt = vip_table.top();
        int end_time = min(nt.fin_time, vt.fin_time);

        if (end_time >= 21 * 3600) break;//如果连此时最早服务完的人都超过21点了那就直接break掉吧

        if (vp.arrive_time <= end_time && end_time == vt.fin_time) assign(vip_player, vip_table);//如果现在vip球桌空出且队列中有vip球员，则vip先上
        else if (np.arrive_time < vp.arrive_time) {//如果普通人先到
            //注意这里的nt是table类型的，我们重载了它的>，所以他会先比较结束时间,谁先结束谁先分配,然后在比较idx,谁id小谁先分配
            if (nt > vt) assign(normal_player, vip_table);
            else assign(normal_player, normal_table);
        }
        else {//vip球员先到
            if (nt > vt)  assign(vip_player, vip_table);
            else assign(vip_player, normal_table);
        }

    }

    sort(player.begin(), player.end());
    for (int i = 0; i < player.size(); i++) {
        printDate(player[i].arrive_time);
        printf(" ");
        printDate(player[i].start_time);
        printf(" %d\n", player[i].waiting_time);
    }

    cout << serve_cnt[1];
    for (int i = 2; i <= k; i++) cout << " " << serve_cnt[i];


    return 0;
}

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
#include <map>
using namespace std;

struct Item
{
    int time;
    bool st;
    bool operator<(Item &i1)const
    {
        return time < i1.time;
    }
};

struct Bill
{
    int begin;
    int end;
};

int costs[24];
int n,m;
unordered_map<string, vector<Item>> items;

map<string, vector<Bill>> maps;

const int N = 1e5;
int s[N];

int timeToInt(int dd,int hh,int mm) {
    return dd * 1440 + hh * 60 + mm;
}

int main() {
    for (int i = 0; i < 24; i++) cin >> costs[i];
    cin >> n;
    while (n--)
    {
        string name,st;
        int dd, hh, mm;
        cin >> name;
        scanf("%d:%d:%d:%d", &m, &dd, &hh, &mm);
        cin >> st;
        bool t = st == "on-line" ? true : false;
        items[name].push_back({ timeToInt(dd,hh,mm),t });
    }
    //过滤掉不合法的记录
    for (auto p : items) {
        auto &v = p.second;
        sort(v.begin(), v.end());
        for (int i = 1; i < v.size();i++) {
            if (v[i - 1].st&&!v[i].st) {
                maps[p.first].push_back({ v[i - 1].time,v[i].time });
                i++;
            }
        }
    }

    int last = 0;
    //预处理每个时刻到 0号:23:59的钱
    for (int d = 1; d <= 31; d++) {
        for (int h = 0; h <= 23; h++) {
            for (int m = 0; m <= 59; m++) {
                int times = timeToInt(d, h, m);
                s[times] += s[last] + costs[h];
                last = times;
            }
        }
    }

    for (auto i : maps) {
        string name = i.first;
        auto &v = i.second;
        printf("%s %02d\n", name.c_str(), m);
        double sum = 0;
        for (int j = 0; j < v.size(); j++) {
            //注意begin-1是前缀和的要求，而end-1是本题的要求，因为最后一段的话费算的其实是end-1~end这一分钟的话费，
            //但是如果直接用s[end]的话，那么最后一段是算的end~end+1这一段的话费,这是由于我们前缀和的求法造成的，
            double money = (double)(s[v[j].end-1] - s[v[j].begin-1]) / 100;
            sum += money;
            printf("%02d:%02d:%02d ", v[j].begin / 1440, v[j].begin %  1440 / 60, v[j].begin % 60);
            printf("%02d:%02d:%02d ", v[j].end / 1440, v[j].end % 1440 / 60, v[j].end % 60);
            printf("%d $%.2lf\n", (v[j].end - v[j].begin), money);
        }
        printf("Total amount: $%.2lf\n", sum);
    }
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define  fi first
#define  se second

typedef pair<int, int> PII;
typedef pair<int, string> PIS;

unordered_map<char, vector<PIS>> levelMap;//PSI:分数，卡号
unordered_map<string, PII> siteMap;//PII:总人数，总分数
unordered_map<string, unordered_map<string,int>> dateMapsTmp;
unordered_map<string, vector<PIS>> dateMaps;//PIS:总人数，site号
int n, m;

bool cmp(PIS &p1,PIS&p2) {
    if (p1.fi != p2.fi) return p1.fi > p2.fi;
    return p1.se < p2.se;
}

int main() {
    scanf("%d%d", &n, &m);
    while (n--)
    {
        string idNum;
        int score;
        cin >> idNum >> score;
        char rank = idNum[0];
        string site = idNum.substr(1, 3);
        string date = idNum.substr(4, 6);
        levelMap[rank].push_back({ score,idNum });
        siteMap[site].fi++; siteMap[site].se += score;
        dateMapsTmp[date][site]++;
    }

    for (auto i : dateMapsTmp) {
        for (auto j : i.se) {
            dateMaps[i.fi].push_back({ j.se,j.fi });
        }
    }

    for (auto &i : levelMap) {
        sort(i.se.begin(), i.se.end(), cmp);
    }

    for (auto &i : dateMaps) {
        sort(i.se.begin(), i.se.end(), cmp);
    }

    for (int T = 1; T <= m; T++) {
        printf("Case %d: ", T);
        int type;
        string term;
        cin >> type >> term;
        cout << type << " " << term << endl;

        bool flag = true;
        if (type == 1) {
            if (levelMap.count(term[0]) == 0) flag = false;
            else {
                for (auto p : levelMap[term[0]]) {
                    cout << p.se << " " << p.fi << endl;
                }
            }
        }
        else if (type == 2) {
            if (siteMap.count(term) == 0) flag = false;
            else
                cout << siteMap[term].fi << " " << siteMap[term].se << endl;
        }
        else {
            if (dateMaps.count(term) == 0) flag = false;
            else {
                for (auto p : dateMaps[term]) {
                    cout << p.se << " " << p.fi << endl;
                }
            }
        }
        if (!flag) puts("NA");
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace  std;

const int  N = 1010;

vector<int> hobby[N];

int p[N],cnt[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int k;
        scanf("%d:", &k);
        while (k--)
        {
            int x;
            scanf("%d", &x);
            hobby[x].push_back(i);
        }
    }

    for (int i = 1; i < n; i++) p[i] = i;

    for (int i = 1; i < N; i++) {
        for (int j = 1; j < hobby[i].size(); j++) {
            int a = hobby[i][0], b = hobby[i][j];
            int pa = find(a), pb = find(b);
            //cout << a << " " << b << endl;
            p[pa] = pb;

        }
    }

    for (int i = 0; i < n; i++) cnt[find(i)]++;

    sort(cnt, cnt + n, greater<int>());

    int k = 0;
    while (cnt[k]) k++;
    cout << k << endl;
    cout << cnt[0];
    for (int i = 1; i < k; i++) cout << " " << cnt[i];


    return 0;
}

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N = 10010;
int pre[N],inord[N],seg[N];
int p[N],depth[N];
unordered_map<int,int> pos;
int m,n;

int build(int il,int ir,int pl,int pr,int d){
    int root=pre[pl];
    int k=root;
    depth[k]=d;
//    puts("-1");
    if(k>il) p[build(il,k-1,pl+1,pl+1+k-1-il,d+1)]=k;
    if(k<ir) p[build(k+1,ir,pl+1+k-1-il+1,pr,d+1)]=k;
    return root;
}

int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>seg[i];
        pos[seg[i]]=i;
        inord[i]=i;
    }
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        pre[i]=pos[x];
    }

    build(0,n-1,0,n-1,0);

    while(m--){
        int a,b;
        cin>>a>>b;
        if(pos.count(a)&&pos.count(b)){
            a=pos[a],b=pos[b];
            int x=a,y=b;
            while(a!=b){
                if(depth[a]>depth[b]) a=p[a];
                else b=p[b];
            }
            if(a!=x&&a!=y) printf("LCA of %d and %d is %d.\n",seg[x],seg[y],seg[a]);
            else if(a==x) printf("%d is an ancestor of %d.\n",seg[x],seg[y]);
            else if(a==y) printf("%d is an ancestor of %d.\n",seg[y],seg[x]);
        }else if(pos.count(a)) printf("ERROR: %d is not found.\n",b);
        else if(pos.count(b)) printf("ERROR: %d is not found.\n",a);
        else printf("ERROR: %d and %d are not found.\n",a,b);
    }

    return 0;
}

本题找LCA的方法如下:

1. 比较a,b点的层数，如果depth[a]>depth[b]，则a往上移动，否则b往上移动;
2. 循环1，直到a,b移动到同一个节点为止。

代码

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N = 10010;
int m,n;
int pre[N],inord[N],seq[N];//seq存的是真正的值,而pre,inord中存的是映射过后的下标
int p[N];//存的是节点的父节点
int depth[N];//存的是每个节点的深度
unordered_map<int,int> pos;

int build(int il,int ir,int pl,int pr,int d){
    int root=pre[pl];
    int k=root;
    depth[k]=d;
    if(k>il) p[build(il,k-1,pl+1,pl+1+k-1-il,d+1)]=k;
    if(k<ir) p[build(k+1,ir,pl+1+k-1-il+1,pr,d+1)]=k;
    return root;
}

int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>pre[i];
        seq[i]=pre[i];
    }
    sort(seq,seq+n);
    for(int i=0;i<n;i++){
        pos[seq[i]]=i;
        inord[i]=i;
    }

    for(int i=0;i<n;i++) pre[i]=pos[pre[i]];

    build(0,n-1,0,n-1,0);

    while(m--){
        int a,b;
        cin>>a>>b;

        if(pos.count(a)&&pos.count(b)){//如果a,b都能够在树中找到
            a=pos[a];b=pos[b];
            int u=a,v=b;
            while(a!=b){
                if(depth[a]>depth[b]) a=p[a];
                else b=p[b];
            }
            if(a!=u&&a!=v) printf("LCA of %d and %d is %d.\n",seq[u],seq[v],seq[a]);
            else if(a==v) printf("%d is an ancestor of %d.\n",seq[v],seq[u]);
            else if(a==u) printf("%d is an ancestor of %d.\n",seq[u],seq[v]);
        }else if(pos.count(a)) printf("ERROR: %d is not found.\n",b);
        else if(pos.count(b)) printf("ERROR: %d is not found.\n",a);
        else printf("ERROR: %d and %d are not found.\n",a,b);
    }

    return 0;
}

本题找LCA的方法如下:

1. 比较a,b点的层数，如果depth[a]>depth[b]，则a往上移动，否则b往上移动;
2. 循环1，直到a,b移动到同一个节点为止。

代码

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N = 10010;
int m,n;
int pre[N],inord[N],seq[N];//seq存的是真正的值,而pre,inord中存的是映射过后的下标
int p[N];//存的是节点的父节点
int depth[N];//存的是每个节点的深度
unordered_map<int,int> pos;

int build(int il,int ir,int pl,int pr,int d){
    int root=pre[pl];
    int k=root;
    depth[k]=d;
    if(k>il) p[build(il,k-1,pl+1,pl+1+k-1-il,d+1)]=k;
    if(k<ir) p[build(k+1,ir,pl+1+k-1-il+1,pr,d+1)]=k;
    return root;
}

int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>pre[i];
        seq[i]=pre[i];
    }
    sort(seq,seq+n);
    for(int i=0;i<n;i++){
        pos[seq[i]]=i;
        inord[i]=i;
    }

    for(int i=0;i<n;i++) pre[i]=pos[pre[i]];

    build(0,n-1,0,n-1,0);

    while(m--){
        int a,b;
        cin>>a>>b;

        if(pos.count(a)&&pos.count(b)){//如果a,b都能够在树中找到
            a=pos[a];b=pos[b];
            int u=a,v=b;
            while(a!=b){
                if(depth[a]>depth[b]) a=p[a];
                else b=p[b];
            }
            if(a!=u&&a!=v) printf("LCA of %d and %d is %d.\n",seq[u],seq[v],seq[a]);
            else if(a==v) printf("%d is an ancestor of %d.\n",seq[v],seq[u]);
            else if(a==u) printf("%d is an ancestor of %d.\n",seq[u],seq[v]);
        }else if(pos.count(a)) printf("ERROR: %d is not found.\n",b);
        else if(pos.count(b)) printf("ERROR: %d is not found.\n",a);
        else printf("ERROR: %d and %d are not found.\n",a,b);
    }

    return 0;
}