2020 年百度之星·程式設計大賽 - 初賽三

2020 年百度之星·程式設計大賽 - 初賽三解題思路及代碼（Discount、Game、Permutation）

1、Discount

Problem Description

學皇來到了一個餐館吃飯。他覺得這家餐館很好吃，于是就想辦個會員。

一共有 nn 種會員儲值卡套餐，假設學皇這餐飯的消費為 a 元，選擇第 ii 種套餐，需要充值 b[i] * a 的錢，這次吃飯可以打 c[i]×10 折，由充值的錢支付（即這次吃飯隻需要從充值金額中扣除 a×c[i] 元）。以後用剩餘的充值的錢吃飯不再打折。

請問學皇應該選擇哪個套餐（必須選擇恰好一個套餐），使得優惠的比例最大？

優惠比例的定義是把充的錢用完以後，(本來應該付的錢 - 實際付的錢) / 本來應該付的錢。在這個題目裡，實際付的錢就是這次充值的花費。

Input

第一行一個整數 test(1≤test≤100) 表示資料組數。

對于每組資料，第一行一個正整數 n(1 \leq n \leq 100)n(1≤n≤100) 表示套餐的數目。

接下來 nn 行，每行一個正整數 b[i] (1≤b[i]≤100) 和一個小數 c[i](0≤c[i]≤1，c[i] 最多包含兩位小數)。

Output

對于每組資料，輸出一個五位小數表示最大的優惠比例。如果小數點後超過五位，四舍五入到五位。

Sample Input

1

2

2 0.5

3 0.1

Sample Output

0.23077

樣例解釋

對于第一種套餐，優惠比例為 0.5a / (2a + 0.5a） = 0.2；

對于第二種套餐，優惠比例為 0.9a / (3a + 0.9a） = 9 / 39；

閱讀題目，會感覺有點複雜，而且一些表達并不好了解，而這道題關鍵在于Sample Output，它給出了樣例的解釋說明，直覺可以判斷出題目最大優惠比例的計算方式，後續很容易解出題目。

Accept代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int test,i,j,n;
    float c[105],b[105];
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        float r1=0.0,r=0.0;
        for(i=0;i<n;i++)
            scanf("%f%f",&b[i],&c[i]);
        for(i=0;i<n;i++)
        {
            if((1-c[i])/(b[i]+1-c[i])>r)//計算每種方案的優惠比例，取最大值
                r=(1-c[i])/(b[i]+1-c[i]);
        }
        printf("%.5f\n",r);    
    }
    return 0;
}       

2、Game

Problem Description

Alice 和 Bob 在玩遊戲。

桌面上有兩堆金币，少的那堆有 x 個金币，多的那堆有 2x 個金币。

假設金币可以被無限細分。Alice 和 Bob 事先都不知道 x 是幾，但是他們都知道 x 是一個 (0,1] 之間均勻分布的随機實數。

Alice 會等機率的被配置設定到其中的一堆金币，Bob 會得到另一堆。xx 的值和兩堆金币的配置設定是互相獨立的。

拿到金币以後，Alice 會馬上數清自己拿到多少金币。然後 Alice 可以選擇是否和 Bob 那堆換。

給定 Alice 拿到的金币數目，請問 Alice 要不要交換，使得她期望能得到的金币數目更多？

如果交換期望得到的金币數目多于不交換期望得到的金币數目，輸出交換，否則不交換。

Input

第一行一個正整數 test (1≤test≤200000) 表示資料組數。

接下來每行一個小數 p (0<p≤2)，p 最多保留五位小數，表示 Alice 拿到的金币數目。

Output

對于每組資料，輸出 Yes 表示需要交換，輸出 No 表示不要交換。

Sample Input

1

1.00000

Sample Output

Yes

先看了題目，差點被誤導為難題，其實看了程式太簡單了，實際了解起來類似于博弈問題，當Alice在遊戲中要獲得更多期望金币，必須從機率方面進行預測。

簡而言之，當p>1時，Alice一定就是得到最大那堆金币了，是以一定不交換，因為p=2*x，x 是一個 (0,1] 之間均勻分布的随機實數；反之，當p<=1,存在Bob可能獲得最大金币，是以Alice選擇交換可能獲得最大金币。

雖然存在Alice拿到0.8，Bob拿到0.4或者1.6，但是還是交換為好，碰運氣。

目前官方提示： 當 p > 1 時，alice 拿到的一定是大的那部分，是以一定不換； 否則，alice 交換以後有一半機率翻倍，一般機率減半，0.25+0.50.5=1.25，是以一定換。

Accept代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int test;
    float p;
    cin>>test;
    while(test--)
    {
        cin>>p;
        if(p>1.0)
            cout<<"No\n";
        else
            cout<<"Yes\n";
    }
    return 0;
}      

3、Permutation

Problem Description

一開始有 n 個數，他們按 1…n 的順序排列，要求交換最多 m 對數字（同一個數字可以參與多次交換），使得逆序對數目最大。

對于一個序列 A，如果存在正整數 i,j 使得 1≤i<j≤n 而且 A[i] > A[j]A[i]>A[j]，則 <A[i],A[j]> 這個有序對稱為 A 的一個逆序對。

Input

第一行一個正整數test (1≤test≤100000) 表示資料組數。

對于每組資料，一行兩個整數 n，m (1≤n≤1000000,0≤m≤1000000) 表示數字個數和最多可以交換的數字對數。

Output

對于每組資料，一行一個整數表示答案。

Sample Input

6

1 1

2 0

2 1

3 1

4 1

4 2

Sample Output

1

3

5

6

看到題目，在紙上寫幾個簡單樣例，就很容易發現這是一個找數學規律的題目，可推導出3種情況，具體見代碼了解不難。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int test,n,m,i;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&m);
        int nums=0;
        if(n==1||m==0)
            nums=0;
        else if(m>=n/2)//當交換次數>=數值向下取整的一半，退化為1+2+……+n-1之和
        {
//            for(i=1;i<=n-1;i++)
//                nums+=i;
                nums=n*(n-1)/2;//數學求和公式代替循環
        }
        else
        {
            int minum=n-2*m;//此題關鍵，推導一般的情況，得到的逆序對
//            for(i=minum;i<=n-1;i++)
//                nums+=i;
                nums=(minum+n-1)*(n-minum)/2;//數學求和公式代替循環
        }
        printf("%d\n",nums);
    }
    return 0;
}      

目前官方提示：

當 m≥⌊n/2⌋ 時，一定能變成 n...1，這時逆序對數最大。否則我們依次交換 1 和 n，2 和 n-1，.....，一共交換 m 對。

但是一個問題暫未解決，測試完全正确，而出現逾時問題，可以看到我用數學求和公式代替循環，考慮可以解決問題，但是送出居然錯誤，還未找出原因。希望有大佬可以評論區提出方法，或者之後我解決了會更新AC代碼。

我的部落格園：

我的CSDN部落格：https://blog.csdn.net/Charzous/article/details/107596506

————————————————

版權聲明：本文為CSDN部落客「Charzous」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：https://blog.csdn.net/Charzous/article/details/107596506