b265: Q11286 - Conformity

https://zerojudge.tw/ShowProblem?problemid=b265

需要用到 struct, sort, 且較難想的題目

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int N;
struct Student{
    int course[5];
}student[10005];

bool cmp( Student A, Student B ){
    for ( int i = 0 ; i < 5 ; i++ )
        if ( A.course[i] != B.course[i] )
            return A.course[i] < B.course[i];
    return false;
}

bool same( int x , int y ){
    for ( int i = 0 ; i < 5 ; i++ )
        if ( student[x].course[i] != student[y].course[i] )
            return false;    
    return true;
}

int main(){
    while ( cin >> N ){
        if ( N == 0 ) break;
        int x;
        for ( int i = 1 ; i <= N ; i++ ){
            for ( int j = 0 ; j < 5 ; j++ ){
                cin >> student[i].course[j];
            }
            sort( student[i].course, student[i].course+5 );
        }

        sort( student+1 , student+N+1 , cmp );    

        int longest = 1, now = 1, ans = 0;

        for ( int i = 2 ; i <= N ; i++ ){
            if ( same( i, i-1 ) ){
                now++;
                if ( now > longest )
                    longest = now;
            }
            else
                now = 1;
        }
        now = 1;
        if ( now == longest ) ans++;

        for ( int i = 2 ; i <= N ; i++ ){
            if ( same( i, i-1 ) ){
                now++;
            }
            else
                now = 1;
            if ( now == longest )
                ans += longest;
        }

        cout << ans << endl;


    }


    return 0;
}

Allen註解版

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int N;

struct Student{
    int course[5];
}student[10005];

//比較兩個學生的所有課程編號大小
bool cmp( Student A, Student B ){
    for ( int i = 0 ; i < 5 ; i++ )
        if ( A.course[i] != B.course[i] )
            return A.course[i] < B.course[i];
    return false;
}

//檢測兩個學生的所有課程是否一樣
bool same( int x , int y ){
    for ( int i = 0 ; i < 5 ; i++ )
        if ( student[x].course[i] != student[y].course[i] )
            return false;
    return true;
}

int main(){

    //N位學生
    while ( cin >> N ){
        if ( N == 0 ) break;
        int x;

        //輸入每位學生所選的課程，最後把課程先排序
        for ( int i = 1 ; i <= N ; i++ ){
            for ( int j = 0 ; j < 5 ; j++ ){
                cin >> student[i].course[j];
            }
            sort( student[i].course, student[i].course+5 );
        }

        //將學生們也進行排序，依照他們所選的課當依據
        sort( student+1 , student+N+1 , cmp );

        //longest代表最多人選的課程組合，有多少人選
        //now暫存的變數，紀錄相同的課程組合，重複出現幾次
        //ans是最後的答案
        int longest = 1, now = 1, ans = 0;

        //掃過每位學生，找出最多人選的組合，總共有多少人選
        for ( int i = 2 ; i <= N ; i++ ){
            if ( same( i, i-1 ) ){
                now++;//該位同學與前一位同學的選課一模一樣，課程重複次數增加
                if ( now > longest )
                    longest = now;//新的最熱門課程誕生
            }
            else
                now = 1;//該位學生與前位學生的選課不同，重複次數重新計算
        }

        now = 1;
        //最熱門課程只有一人，代表大家選的都不同，每位學生的組合都是最熱門的組合
        if ( now == longest ) ans++;

        //檢查最多人選的課程是否不只一種組合，如果longest是3，裡面有兩個課程組合各有3人選的話
        //那就是3+3，答案就是6
        //裡面比較特別的是當每種組合都不同，要把答案先+1
        for ( int i = 2 ; i <= N ; i++ ){
            if ( same( i, i-1 ) ){
                now++;
            }
            else
                now = 1;

            if ( now == longest )
                ans += longest;
        }

        cout << ans << endl;


    }


    return 0;
}