1829. 发愁

10175102262 LarsPendragon

求问最佳算法(附上自己的弱算法(1169B,0.000s))

#include <stdio.h>
void quickSort(long long *a, int low, int high)
{
    if(low >= high)
        return;
    int i=low, j=high;
    long long key=a[low];
    while(i<j)
    {
        while(i<j && key<=a[j])
            j--;
        a[i]=a[j];
        while(i<j && key>=a[i])
            i++;
        a[j]=a[i];
    }
    a[i]=key;
    quickSort(a, low, i-1);
    quickSort(a, i+1, high);
}
int main(void)
{
    int m, n, I, i;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0) break;
        long long s[n];
        for(i=0; i<n; i++){
            s[i]=i+1;
            s[i]+=30000000000LL;}
        //for(i=0; i<n; i++) printf("%lld\n",s[i]);
        for(I=0; I<m; I++)
        {
            int a, b, c;
            scanf("%d%d%d",&a,&b,&c);
            if(c==1){
                s[a-1]-=300000000;
                s[a-1]+=100000;
                s[b-1]+=100000000;
                s[b-1]+=100;
            }else if(c==-1){
                s[b-1]-=300000000;
                s[b-1]+=100000;
                s[a-1]+=100000000;
                s[a-1]+=100;
            }else{
                s[a-1]-=100000000;
                s[b-1]-=100000000;
            }
        //for(i=0; i<n; i++) printf("%lld\n",s[i]); 
        }
        for(i=0; i<n; i++)
            s[i]=(s[i]-200000*((s[i]/100000)%1000)+99900000);
        quickSort(s, 0, n-1);
        for(i=0; i<n; i++){
            if(i==n-1) printf("%d\n",s[i]%100);
            else printf("%d ",s[i]%100);}
    }
    return 0;
}
Suzuki_Yuuta

别问,问就说结构体排序,稳得一批。

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

struct team {
    int id;
    int score; 
    int winNum, loseNum;
};

bool cmp(const team& A, const team& B) {
    if (A.score == B.score) {
        if (A.winNum == B.winNum) {
            if (A.loseNum == B.loseNum) {
                return (A.id < B.id);
            }
            return (A.loseNum < B.loseNum);
        }
        return (A.winNum > B.winNum);
    }
    return (A.score > B.score);
}

void solve(int teamNum, int playNum)
{
    team* data = new team[teamNum];
    for (int i = 0; i < teamNum; i++) {
        data[i].id = i + 1; data[i].score = 0;
    }
    for (int i = 0; i < playNum; i++) {
        int teamA, teamB, judge;
        cin >> teamA >> teamB >> judge;
        if (judge == 1) {
            data[teamA - 1].score += 3; data[teamA - 1].winNum += 1;
            data[teamB - 1].score -= 1; data[teamB - 1].loseNum += 1;
        } else if (judge == -1) {
            data[teamA - 1].score -= 1; data[teamA - 1].loseNum += 1;
            data[teamB - 1].score += 3; data[teamB - 1].winNum += 1;
        } else if (judge == 0) {
            data[teamA - 1].score += 1;
            data[teamB - 1].score += 1;
        }
    }
    sort(data, data + teamNum, cmp);
    for (int i = 0; i < teamNum; i++) {
        cout << data[i].id << ((i + 1 == teamNum) ? "\n" : " ");
    }
}

int main(int argc, char* argv[]) {
    int teamNum, playNum;
    while (cin >> teamNum >> playNum) {
        cin.ignore();
        if (teamNum == 0 && playNum == 0) {
            break;
        }
        solve(teamNum, playNum);
    }
    return 0;
}
Deuchie

注意,最好不要像楼上那样用「变长数组」(VLA)。

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

int main() {
    uint32_t n, m;
    while (cin >> n >> m, n || m) {
        if (n == 0) {
            cout.put('\n');
            continue;
        }
        struct Team {
            uint32_t id;
            int32_t score = 0;
            uint32_t win_cnt = 0;
            uint32_t lose_cnt = 0;
        };
        vector<Team> teams(n + 1);
        for (uint32_t i = 1; i <= n; ++i)
            teams[i].id = i;
        for (uint32_t i = 0; i < m; ++i) {
            uint32_t a, b; int32_t c; cin >> a >> b >> c;
            if (c == 1) {
                teams[a].score += 3;
                --teams[b].score;
                ++teams[a].win_cnt;
                ++teams[b].lose_cnt;
            } else if (c == -1) {
                teams[b].score += 3;
                --teams[a].score;
                ++teams[b].win_cnt;
                ++teams[a].lose_cnt;
            } else {
                ++teams[a].score;
                ++teams[b].score;
            }
        }
        sort(teams.begin() + 1, teams.end(), [](Team const &a, Team const &b) {
            if (a.score == b.score) {
                if (a.win_cnt == b.win_cnt) {
                    if (a.lose_cnt == b.lose_cnt)
                        return a.id < b.id;
                    else
                        return a.lose_cnt < b.lose_cnt;
                } else
                    return a.win_cnt > b.win_cnt;
            } else
                return a.score > b.score;
        });
        cout << teams[1].id;
        for (uint32_t i = 2; i <= n; ++i)
            cout << ' ' << teams[i].id;
        cout.put('\n');
    }
}
Deuchie

如果让现在的我来写我一定不会写这么丑……

Low Coder

空格。。。最后一个数后也需输出空格 再输出换行
如题

10154601131

没想到,我逃过了空格,却没逃过m=0
如题
此题真是视力不佳者的劫难

你当前正在回复 博客/题目
存在问题!