比賽：Codeforces Round 931 (Div. 2) (A~B)

目錄：A B

A題：Too Min Too Max

標簽: 構造算法（constructive algorithms）貪心（greedy）數學（math）

題目大意

• 對數組 a 找到四個不同下標 i, j, k, l ，最大化：
• • |a_i ? a_j| + |a_j ? a_k| + |a_k ? a_l| + |a_l ? a_i|

思路

• 因為選擇四個數構成一個環，去相鄰差值和，貪心四個值應該 大數 小數 大數 小數 交替擺放，可以證明這是最優的
• 一個數最多出現一次，所以找到最大，次大值，最小，次小值交替擺放即可

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
void solve()
{int n; cin >> n;for(int i = 0; i < n; i++)cin >> a[i];sort(a, a + n);cout << (a[n-1]+a[n-2]-a[0]-a[1])*2 << '\n';
} 
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

B題：Yet Another Coin Problem

標簽: 暴力枚舉（brute force）動態規劃（dp）貪心（greedy）數學（math）

題目大意

• 有 5 種不同的硬幣，面額為1 3 6 10 15
• 找出所需的最少數量的這些硬幣，使它們的總價值相加正好是 n （1 ≤ n ≤ 10⁹)

思路

• 貪心：1 3 6 10 15最大公約數是30，除了小于30的部分其他用15面額的硬幣填充
• 小于30的部分用dp即可，完全背包問題。當然手動模擬也行反正沒幾項hh
• 選擇n / 15 - 1個15面額的硬幣，剩余錢數n%15+15 dp即可

AC代碼

#include <bits/stdc++.h>
using namespace std;
int dp[30]={0,1,2,1,2,3,1,2,3,2,1,2,2,2,3,1,2,3,2,3,2,2,3,3,3,2,3,3,3,4};
void solve()
{int n; cin >> n;  if(n < 30) cout << dp[n] << endl; else cout << n / 15 - 1 + dp[n % 15 + 15] << endl;
} 
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

// dp數組計算方式，完全背包問題
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int v[5] = {1, 3, 6, 10, 15};
int dp[N]; 
void solve()
{int n; cin >> n;  if(n < 30) cout << dp[n] << endl; else cout << n / 15 - 1 + dp[n % 15 + 15] << endl;
} 
int main()
{memset(dp, 0x3f, sizeof dp); dp[0] = 0;for(int i = 0; i < 5; i++)for(int j = v[i]; j < N; j++)dp[j] = min(dp[j], dp[j-v[i]] + 1);int T; cin >> T;while(T--)solve();return 0;
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*__   _,--="=--,_   __/  \."    .-.    "./  \/  ,/  _   : :   _  \/` \\  `| /o\  :_:  /o\ |\__/`-'| :="~` _ `~"=: |\`     (_)     `/.-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.)  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				))                                     (
'---------------------------------------'
*/