解題思路

這道題是華一高2020級(jí)信息學(xué)競(jìng)賽班在八月份一次考試中的T3。

作為一名新初一學(xué)生，在題目里看到這么復(fù)雜的數(shù)學(xué)公式時(shí)我的心情是崩潰的。

讀題完全在讀是天書

但其實(shí)這題也沒(méi)有那么難，裸的模擬。

首先，解釋一下我定義的變量。

struct stures{            // 存儲(chǔ)每個(gè)選手的數(shù)據(jù)
    int id;                 // 選手編號(hào)
    double yv;              // 總位置分
  double sumv;            // 總分
}res[1005];
int n;                    // 題目中N
int x[1005][10] = {};     // 題目中x
double y[1005][10] = {};  // 題目中y
double avg[10] = {};      // 題目中avg

接下來(lái)我們用文字語(yǔ)言來(lái)解釋一下那些求和公式。

• 第

  
  項(xiàng)競(jìng)賽的平均分
  

  求平均分應(yīng)該沒(méi)有不會(huì)的吧。將每位選手第

  
  項(xiàng)競(jìng)賽的分?jǐn)?shù)加起來(lái)，除以選手個(gè)數(shù)就是第
  
  項(xiàng)競(jìng)賽的平均分了。

  代碼實(shí)現(xiàn)：

  for(int i = 0; i < 8; i++){                                            // 算均分 
      for(int j = 0; j < n; j++) avg[i] += x[j][i];
      avg[i] /= n;
  }
  

• 選手

  
  的總分
  

  這也不難理解，將選手每項(xiàng)競(jìng)賽的分?jǐn)?shù)加起來(lái)就是了。

  代碼實(shí)現(xiàn)：

  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)                  // 算總分 
      res[i].sumv += x[i][j];
  

• 選手

  
  第
  
  項(xiàng)競(jìng)賽的位置分
  
  
  這個(gè)有點(diǎn)復(fù)雜，首先來(lái)弄懂后面括號(hào)的內(nèi)容。

  首先，#define 分差 競(jìng)賽得分與均分的差

  
  這個(gè)式子就是選手
  
  的分差之和。

  若分差之和為

  
  ，則選手
  
  競(jìng)賽
  
  位置值為
  
  。

  若分差之和不為

  
  ，則位置值取選手
  
  競(jìng)賽
  
  的分差除以選手
  
  所有競(jìng)賽分差的平均值。

  讀不懂就仔細(xì)多讀幾遍吧，我寫的不好。

  代碼實(shí)現(xiàn)：

  for(int i = 0; i < 8; i++) for(int j = 0; j < n; j++){                 // 算位置分 
      for(int k = 0; k < n; k++) y[j][i] += abs(x[k][i] - avg[i]);
      if(y[j][i] != 0) y[j][i] = (x[j][i] - avg[i]) / (y[j][i] / n);
  }
  

• 選手

  
  的總位置分
  

  也就是說(shuō)，在總位置分中，前三項(xiàng)競(jìng)賽的位置分權(quán)值為1，后五項(xiàng)的權(quán)值為0.8，求和即可。

  代碼實(shí)現(xiàn)：

  for(int i = 0; i < n; i++){                                            // 算總位置分 
      res[i].id = i;
      res[i].sumv = 0;
      for(int j = 0; j < 3; j++) res[i].yv += y[i][j];
      for(int j = 3; j < 8; j++) res[i].yv += 0.8 * y[i][j];
  }
  

  在這里順便為res數(shù)組作初始化

以上工作做完以后，我們?cè)俑鶕?jù)排名規(guī)則寫一個(gè)cmp函數(shù)：

bool cmp(stures r1, stures r2){
    if(r1.yv != r2.yv) return r1.yv > r2.yv;
    else if(r1.sumv != r2.sumv) return r1.sumv > r2.sumv;
    else return r1.id < r2.id;
}

就是這樣，

AC CODE

#include<bits/stdc++.h>
using namespace std;
struct stures{
    int id;
    double yv, sumv;
}res[1005];
bool cmp(stures r1, stures r2){
    if(r1.yv != r2.yv) return r1.yv > r2.yv;
    else if(r1.sumv != r2.sumv) return r1.sumv > r2.sumv;
    else return r1.id < r2.id;
}
int main(){
//  freopen("ranking.in", "r", stdin);
//  freopen("ranking.out", "w", stdout);
    int n, x[1005][10] = {};
    double y[1005][10] = {}, avg[10] = {};
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < 8; j++) cin >> x[i][j];  // 輸入 
    for(int i = 0; i < 8; i++){                                            // 算均分 
        for(int j = 0; j < n; j++) avg[i] += x[j][i];
        avg[i] /= n;
    }
    for(int i = 0; i < 8; i++) for(int j = 0; j < n; j++){                 // 算位置分 
        for(int k = 0; k < n; k++) y[j][i] += abs(x[k][i] - avg[i]);
        if(y[j][i] != 0) y[j][i] = (x[j][i] - avg[i]) / (y[j][i] / n);
    }
    for(int i = 0; i < n; i++){                                            // 算總位置分 
        res[i].id = i;
        res[i].sumv = 0;
        for(int j = 0; j < 3; j++) res[i].yv += y[i][j];
        for(int j = 3; j < 8; j++) res[i].yv += 0.8 * y[i][j];
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)                  // 算總分 
        res[i].sumv += x[i][j];
    sort(res, res+n, cmp);                                                 // 快排 
    for(int i = 0; i < n; i++) cout << res[i].id+1 << endl;                // 輸出 
    return 0;
}

提交記錄

• 用時(shí) 89ms
• 內(nèi)存 832.00KB

我這代碼效率真的低