ZeroJudge 解題筆記：e800. p7. 影片推薦

作者：王一哲
日期：2025年2月4日



ZeroJudge 題目連結：e800. p7. 影片推薦

解題想法

這題考排序，如果用 Python 解題需要用 functools.cmp_to_key 自訂比較式，如果用 C++ 可以在 sort 裡面用 lambda function 寫比較式，也可以將比較式放在外面。

Python 程式碼

使用時間約為 23 ms，記憶體約為 4 MB，通過測試。

from functools import cmp_to_key

def mycmp(a, b):  # 自訂比較用的函式
    pa = a[2]*a[4]*a[5]/a[3]  # a 的優先推薦指數
    pb = b[2]*b[4]*b[5]/b[3]  # b 的優先推薦指數
    if pa > pb: return -1  # 如果 pa 大於 pb，a 往前放
    elif pa < pb: return 1  # 如果 pa 小於 pb，a 往後放
    else:  # 如果 pa 等於 pb
        if a[0] < b[0]: return 1  # 如果 a 的編號較小，a 往前放
        elif a[0] > b[0]: return -1  # 如果 a 的編號較大，a 往後放
        else: return 0  # 如果 a、b 的編號相等，不換順序

N = int(input())  # 影片個數
# 影片資料，內容為 [編號 i, 名稱 S, 觀看人數 P, 影片長度 L, 平均觀看時間 W, 相關係數 R]
data = []
for i in range(1, N+1):  # 讀取 N 行資料
    d = input().split()  # 拆開成串列
    data.append([i, d[0], int(d[1]), int(d[2]), int(d[3]), int(d[4])])  # 加入 data
data.sort(key = cmp_to_key(mycmp))  # 依照 mycmp 排序
for d in data: print(d[1])  # 印出排序後的影片名稱

C++ 程式碼

計算優先推薦指數時如果用 int 會溢位，要用 long。使用時間約為 2 ms，記憶體約為 360 kB，通過測試。

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

/* 影片資料，內容為 [編號 i, 名稱 S, 觀看人數 P, 影片長度 L, 平均觀看時間 W, 相關係數 R] */
struct Video {
    string S;
    long idx, P, L, W, R;
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;  // 影片個數
    vector<Video> data (N);
    for(int i=0; i<N; i++) {  // 讀取 N 行資料
        data[i].idx = i;
        cin >> data[i].S >> data[i].P >> data[i].L >> data[i].W >> data[i].R;
    }
    sort(data.begin(), data.end(), [] (Video a, Video b) {  // 排序
        if (a.P*a.W*a.R*b.L == b.P*b.W*b.R*a.L) return a.idx < b.idx;
        else return a.P*a.W*a.R*b.L > b.P*b.W*b.R*a.L; } );
    for(auto d : data) cout << d.S << "\n";  // 印出排序後的影片名稱
    return 0;
}

也可以把排序用的比較式放到外面。使用時間約為 2 ms，記憶體約為 348 kB，通過測試。

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

/* 影片資料，內容為 [編號 i, 名稱 S, 觀看人數 P, 影片長度 L, 平均觀看時間 W, 相關係數 R] */
struct Video {
    string S;
    long idx, P, L, W, R;
};

bool mycmp(Video a, Video b) {
    if (a.P*a.W*a.R*b.L == b.P*b.W*b.R*a.L) return a.idx < b.idx;
    else return a.P*a.W*a.R*b.L > b.P*b.W*b.R*a.L;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;  // 影片個數
    vector<Video> data (N);
    for(int i=0; i<N; i++) {  // 讀取 N 行資料
        data[i].idx = i;
        cin >> data[i].S >> data[i].P >> data[i].L >> data[i].W >> data[i].R;
    }
    sort(data.begin(), data.end(), mycmp);  // 排序
    for(auto d : data) cout << d.S << "\n";  // 印出排序後的影片名稱
    return 0;
}