e800 - p7. 影片推薦
題目描述
題目要求根據給定的觀看人數、影片長度、平均觀看時間和相關係數，計算每個影片的「優先推薦指數」，並按照該指數由高到低輸出影片名稱。如果多個影片的指數相同，則按照輸入的順序輸出。
解題思路
題目給定了一個計算「優先推薦指數」的公式：觀看人數 * (影片長度 / 平均觀看時間) * 相關係數。解題思路是首先讀取每個影片的資訊，計算其優先推薦指數，然後使用排序演算法將影片按照指數由高到低排序。最後，按照排序後的順序輸出影片名稱。這裡使用了 std::sort 函數和自定義的比較函數 cmp 來實現排序。比較函數首先比較優先推薦指數，如果指數相同，則比較輸入順序（影片編號）。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是影片的數量。這是因為主要的運算時間花費在排序上，
std::sort通常使用快速排序或歸併排序等具有 O(n log n) 時間複雜度的演算法。 - 空間複雜度: O(n)，因為需要儲存所有影片的資訊，包括名稱、觀看人數、影片長度、平均觀看時間、相關係數和優先推薦指數。
程式碼
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct a{
string name;
int no;
float score;
};
bool cmp(a p,a q){
return p.score>q.score;
if(p.score==q.score)
return p.no<q.no;
return p.score<q.score;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int c;
float x,y,k,j;
cin >> c;
a n[c];
for(int i=0;i<c;i++){
cin >> n[i].name ;
cin >> x >> y >> k >> j;
n[i].score=x*(k/y)*j;
n[i].no=i;
}
sort(n,n+c,cmp);
for(int i=0;i<c;i++){
cout << n[i].name <<"\n";
}
}