算法刷題【洛谷P1786】幫貢排序——算法刷題細思極恐現象！

題目背景

在absi2011的幫派裡，死号偏多。現在absi2011和幫主等人聯合決定，要清除一些死号，加進一些新号，同時還要鼓勵幫貢多的人，對幫派進行一番休整。

題目描述

目前幫派内共最多有一位幫主，兩位副幫主，兩位護法，四位長老，七位堂主，二十五名精英，幫衆若幹。

現在absi2011要對幫派内幾乎所有人的職位全部調整一番。他發現這是個很難的事情。于是要求你幫他調整。

他給你每個人的以下資料：

他的名字(長度不會超過30)，他的原來職位，他的幫貢，他的等級。

他要給幫貢最多的護法的職位，其次長老，以此類推。

可是，樂鬥的顯示并不按幫貢排序而按職位和等級排序。

他要你求出最後樂鬥顯示的清單(在他調整過職位後)：職位第一關鍵字，等級第二關鍵字。

注意：absi2011無權調整幫主、副幫主的職位，包括他自己的(這不是廢話麼…)

他按原來的順序給你(是以，等級相同的，原來靠前的現在也要靠前，因為經驗高低的原因，但此處為了簡單點省去經驗。)

輸入格式

第一行一個數n，表示星月家園内幫友的人數。

下面n行每行兩個字元串兩個整數，表示每個人的名字、職位、幫貢、等級。

輸出格式

一共輸出n行，每行包括排序後樂鬥顯示的名字、職位、等級。

輸入輸出樣例

In 1

9
DrangonflyKang BangZhu 100000 66
RenZaiJiangHu FuBangZhu 80000 60
absi2011 FuBangZhu 90000 60
BingQiLingDeYanLei HuFa 89000 58
Lcey HuFa 30000 49
BangYou3 ZhangLao 1000 1
BangYou1 TangZhu 100 40
BangYou2 JingYing 40000 10
BangYou4 BangZhong 400 1

Out 1

DrangonflyKang BangZhu 66
RenZaiJiangHu FuBangZhu 60
absi2011 FuBangZhu 60
BingQiLingDeYanLei HuFa 58
BangYou2 HuFa 10
Lcey ZhangLao 49
BangYou1 ZhangLao 40
BangYou3 ZhangLao 1
BangYou4 ZhangLao 1

标題提到的細思極恐等會再說。

這道題就是一個殘害競賽生的排序啊……

首先存儲每個成員的結構體如下

struct node {
    string name, zw;  // 名字，目前職位
    long long bg, dj, id;  // 幫貢，等級，輸入順序
} a[200], fbz[2];  // a存正常成員，fbz存儲副幫主

首先幫主和副幫主不參與調整，是以對于幫主讀取到之後可以直接輸出，而副幫主兩個輸入之後比較一下誰的等級高先輸出誰就行了（雖然這道題在這裡資料不強，不比較副幫主也是可以ac的，洛谷題解裡很多都沒考慮副幫主的問題，甚至有直接讀入前三行輸出的）

是以在這裡設計輸入如下

long long n;
cin >> n;
for (long long i = 0; i < n; i++) {
    cin >> a[i].name >> a[i].zw >> a[i].bg >> a[i].dj;
    a[i].id = i;  // 輸入的順序，友善過後排序
    if (a[i].zw == "BangZhu") {
    	// 幫主直接輸出
        cout << a[i].name << " " << a[i].zw << " " << a[i].dj << endl;
        // 幫主不存進a裡面，是以i和n要--（下面副幫主同）
        i--;
        n--;
    } else if (a[i].zw == "FuBangZhu") {
    	// 副幫主先存進fbz數組，要比較兩個副幫主的等級之後再輸出
        fbz[fbzl++] = a[i];
        i--;
        n--;
    }
}
if (fbz[0].dj < fbz[1].dj) swap(fbz[0], fbz[1]);  // 看目前兩個副幫主順序是否正确
for (int i = 0; i < 2; i++)
    cout << fbz[i].name << " " << fbz[i].zw << " " << fbz[i].dj << endl;  // 完成副幫主輸出

至此完成了資料輸入和幫主、副幫主的處理。

除此三人之外的其他人按照幫貢第一關鍵字、輸入順序第二關鍵字排序，可以直接結構體+cmp函數+sort實作（雖然按幫貢排序後通常情況相同幫貢會保持先輸入的在前面，但是為了保險還是進行雙關鍵字吧）

對結構體進行排序的cmp函數如下

bool cmp(node x, node y) {
    if (x.bg != y.bg)
        return x.bg > y.bg;  // 幫貢不同幫貢大的在前
    else
        return x.id < y.id;  // 否則排輸入順序
}

很多人說不會cmp函數到底怎麼設計，這裡給大家一個很簡單的了解：cmp函數的參數x和y，如果x在前y在後是正确的return 1，否則return 0，簡單說就是問x在前y在後這個順序對不對

（如果幫到了你還不趕快三連！）

然後就是一個咋看咋好用的sort了

往下我這個方法不是最好的，也很有可能是這裡的書寫才導緻了那個細思極恐的問題，但是作為結構體和sort的練習等還是不錯的

我們再開一個結構體存儲幫主和副幫主之外的職位：

struct Node {
    string name;
    long long cnt;
} zw[10];  // zw就是職位

然後在main函數開頭寫上這一段

zw[0].name = "HuFa";
zw[0].cnt = 2;
zw[1].name = "ZhangLao";
zw[1].cnt = 4;
zw[2].name = "TangZhu";
zw[2].cnt = 7;
zw[3].name = "JingYing";
zw[3].cnt = 25;
zw[4].name = "BangZhong";
zw[4].cnt = 100000000;

衆所周知，sort函數可以排數組的片段

是以我們首先為相同職位的再寫一個cmpp函數

bool cmpp(node x, node y) {
    if (x.dj != y.dj)
        return x.dj > y.dj;
    else
        return x.id < y.id;
}

和上面的cmp類似，不再贅述，就是要注意因為等級相同還是按照輸入順序，是以不要忘了id的比較

最終的排序和輸出，看注釋

long long l = 0, i;
for (i = 0; i < 4; i++) {  // 完成除幫衆外的排序和輸出
    if (n - l >= zw[i].cnt) {
    	// 分析可知從數組索引l（含）到索引l + zw[i].cnt（不含）是目前職位的所有人
        sort(a + l, a + l + zw[i].cnt, cmpp);  // 按照等級和輸入順序排序
        for (long long j = l; j < l + zw[i].cnt; j++)
            cout << a[j].name << " " << zw[i].name << " " << a[j].dj << endl;  // 輸出
        l += zw[i].cnt;  // 左指針自增，在此之前的都處理完了
    } else
        break;  // 如果人數不足以配置設定完目前職位了就跳出
}
if (n - l > 0) {  // 還有沒配置設定的人
    sort(a + l, a + n, cmpp);  // 排序剩下的沒配置設定的所有人
    for (long long j = l; j < n; j++)
        cout << a[j].name << " " << zw[i].name << " " << a[j].dj << endl;
}

這個程式在對于幫衆的處理是沒有bug的，自己嘗試了解一下，實在不懂評論區提問我會解答

然後就附上完整的ac代碼吧（我知道你就是奔着這裡點開這篇文章的不是嗎）

#include <bits/stdc++.h>
using namespace std;

struct node {
    string name, zw;
    long long bg, dj, id;
} a[200], fbz[2];

struct Node {
    string name;
    long long cnt;
} zw[10];

long long fbzl = 0;

bool cmp(node x, node y) {
    if (x.bg != y.bg)
        return x.bg > y.bg;
    else
        return x.id < y.id;
}

bool cmpp(node x, node y) {
    if (x.dj != y.dj)
        return x.dj > y.dj;
    else
        return x.id < y.id;
}

int main() {
    zw[0].name = "HuFa";
    zw[0].cnt = 2;
    zw[1].name = "ZhangLao";
    zw[1].cnt = 4;
    zw[2].name = "TangZhu";
    zw[2].cnt = 7;
    zw[3].name = "JingYing";
    zw[3].cnt = 25;
    zw[4].name = "BangZhong";
    zw[4].cnt = 100000000;

    long long n;
    cin >> n;
    for (long long i = 0; i < n; i++) {
        cin >> a[i].name >> a[i].zw >> a[i].bg >> a[i].dj;
        a[i].id = i;
        if (a[i].zw == "BangZhu") {
            cout << a[i].name << " " << a[i].zw << " " << a[i].dj << endl;
            i--;
            n--;
        } else if (a[i].zw == "FuBangZhu") {
            fbz[fbzl++] = a[i];
            i--;
            n--;
        }
    }
    if (fbz[0].dj < fbz[1].dj) swap(fbz[0], fbz[1]);
    for (int i = 0; i < 2; i++)
        cout << fbz[i].name << " " << fbz[i].zw << " " << fbz[i].dj << endl;

    sort(a, a + n, cmp);
    long long l = 0, i;
    for (i = 0; i < 4; i++) {
        if (n - l >= zw[i].cnt) {
            // cout << i << zw[i].name << zw[i].cnt << endl;
            sort(a + l, a + l + zw[i].cnt, cmpp);
            for (long long j = l; j < l + zw[i].cnt; j++)
                cout << a[j].name << " " << zw[i].name << " " << a[j].dj
                     << endl;
            l += zw[i].cnt;
        } else
            break;
    }
    if (n - l > 0) {
        sort(a + l, a + n, cmpp);
        for (long long j = l; j < n; j++)
            cout << a[j].name << " " << zw[i].name << " " << a[j].dj << endl;
    }

    return 0;
}

細思極恐的就是

在我調試程式時

第76行輸出的兩個i居然不一樣！

而且通路不到zw數組中的cnt！

并且似乎不是所有電腦都出現這樣的表現（xth同學試了似乎沒問題？）

代碼放這裡了

高人請指點，必有重謝！！！！

/*輸入資料
9
DrangonflyKang BangZhu 100000 66
RenZaiJiangHu FuBangZhu 80000 60
absi2011 FuBangZhu 90000 60
BingQiLingDeYanLei HuFa 89000 58
Lcey HuFa 30000 49
BangYou3 ZhangLao 1000 1
BangYou1 TangZhu 100 40
BangYou2 JingYing 40000 10
BangYou4 BangZhong 400 1
*/


#include <bits/stdc++.h>
using namespace std;

struct node {
    string name, zw;
    long long bg, dj, id;
} a[200], fbz[2];

struct Node {
    string name;
    long long cnt;
} zw[10];

long long fbzl = 0;

bool cmp(node x, node y) {
    if (x.bg != y.bg)
        return x.bg > y.bg;
    else
        return x.id < y.id;
}

bool cmpp(node x, node y) {
    if (x.dj != y.dj)
        return x.dj > y.dj;
    else
        return x.id < y.id;
}

int main() {
    // freopen("D:/Desktop/11.txt", "r", stdin);
    // freopen("D:/Desktop/1.txt", "w", stdout);

    zw[0].name = "HuFa";
    zw[0].cnt = 2;
    zw[1].name = "ZhangLao";
    zw[1].cnt = 4;
    zw[2].name = "TangZhu";
    zw[2].cnt = 7;
    zw[3].name = "JingYing";
    zw[3].cnt = 25;
    zw[4].name = "BangZhong";
    zw[4].cnt = 100000000;

    long long n;
    cin >> n;
    for (long long i = 0; i < n; i++) {
        cin >> a[i].name >> a[i].zw >> a[i].bg >> a[i].dj;
        a[i].id = i;
        if (a[i].zw == "BangZhu") {
            cout << a[i].name << " " << a[i].zw << " " << a[i].dj << endl;
            i--;
            n--;
        } else if (a[i].zw == "FuBangZhu") {
            fbz[fbzl++] = a[i];
            i--;
            n--;
        }
    }
    if (fbz[0].dj < fbz[1].dj) swap(fbz[0], fbz[1]);
    for (int i = 0; i < 2; i++)
        cout << fbz[i].name << " " << fbz[i].zw << " " << fbz[i].dj << endl;

    // cout << endl;
    sort(a, a + n, cmp);
    for (int i = 0; i < n; i++) cout << a[i].id << " ";
    cout << endl << n << endl;
    long long l = 0, i;
    for (i = 0; i < 3; i++) {
        cout << i << " ";
        if (n - l >= zw[i].cnt) {
            cout << i << " ";
            sort(a + l, a + l + zw[i].cnt, cmpp);
            cout << i << "\n";
            printf("%ld   ", i);
            printf("i:%ld  %ld %ld  i:%ld cnt:%ld\n", i, l, (l + zw[i].cnt), i,
                   zw[i].cnt);
            // for (long long j = l; j < l + zw[i].cnt; j++)
            //     cout << a[j].id << " " << a[j].name << " " << zw[i].name << "
            //     "
            //          << a[j].dj << endl;
            // printf("%ld %ld  i:%ld cnt:%ld\n", l, (l + zw[i].cnt), i,
            //        zw[i].cnt);

            l += zw[i].cnt;
        } else
            break;
    }
    // if (n - l > 0) {
    //     sort(a + l, a + n, cmpp);
    //     for (long long j = l; j < n; j++)
    //         cout << a[j].id << " " << a[j].name << " " << zw[i].name << " "
    //              << a[j].dj << endl;
    // }

    return 0;
}

（少年，這個可不是ac代碼，去掉調試也隻有30分而已）

算法刷題【洛谷P1786】幫貢排序——算法刷題細思極恐現象！

題目背景

題目描述

輸入格式

輸出格式

輸入輸出樣例

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述