8.12信息學集訓_摸底+貪心
摸底賽題
P9955 [USACO20DEC] Do You Know Your ABCs? B
有三個正整數 \(A\)、\(B\) 和 \(C\)（\(A\le B\le C\)）。這些數字范圍在 \(1\ldots 10^9\) 之間的整數（不一定各不相同），并且是 \(A\)、\(B\)、\(C\)、\(A+B\)、\(B+C\)、\(C+A\) 和 \(A+B+C\) 的某種排列。
給定這七個整數，求出 \(A\)、\(B\) 和 \(C\)。可以證明，答案是唯一的。
輸入格式：輸入一行，包含七個空格分隔的整數。
輸出格式：輸出 \(A\)、\(B\) 和 \(C\)，用空格分隔。
in:
2 2 11 4 9 7 9
out:
2 2 7
【分析】7個數字中選3個數，匹配要求，推導一下有如下信息
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int main(int argc, char* argv[]) {
int a[10], n = 7;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
a[3] = a[7] - a[1] - a[2];
cout << a[1] << " " << a[2] << " " << a[3];
return 0;
}
P5436 【XR-2】緣分
一禪和師父約定一個正整數 \(n\)，接著他們各自在心里想一個不超過 \(n\) 的正整數，這兩個數的最小公倍數最大會是多少。
輸入格式：
多組數據，第一行一個正整數 \(T\)，表示數據組數。
接下來的 \(T\) 行，每行一個正整數 \(n\)，表示一禪和師父約定的正整數。
輸出格式：對每組數據，一行一個正整數，表示答案。
in：
1
3
out:
6
【樣例說明】不超過 \(3\) 的兩個正整數的最小公倍數的最大值為 \(\mathrm{lcm}(2,3) = 6\)。
【數據規模與約定】
對 \(50\%\) 的數據，\(1 \le T,n \le 100\)。
對 \(100\%\) 的數據，\(1 \le T \le 100, 1 \le n \le 10^9\)。
【分析】\(a,b\le n,\quad ans = max(lcm(a,b))\)
方法1：枚舉 \(a,b\)，復雜度 \(O(Tn^2)\)，得分 50；
方法2：推導一下，\(lcm(a,b) = a*b/gcd(a,b)\)，想 \(lcm\) 越大，那么 \(a*b\) 越大，\(gcd(a,b)\) 越小
\(gcd(n-1, n)=1\)，所以 \(a=n-1, b=n\)
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
typedef long long ll;
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
// 求 max(lcm(a,b)) = max(a*b/gcd(a,b))，則a b互質就是答案
int main() {
ll t, n;
cin >> t;
while (t--) {
cin >> n;
cout << (n == 1 ? 1 : n * (n - 1)) << endl;
}
return 0;
}
P1182 數列分段 Section II
對于給定的一個長度為 \(N\) 的正整數數列 \(A_{1\sim N}\)，現要將其分成 \(M\)（\(M\leq N\)）段，并要求每段連續，且每段和的最大值最小。
in:
5 3
4 2 4 5 1
out:
6
【數據規模與約定】
對于 \(20\%\) 的數據，\(N\leq 10\)。
對于 \(40\%\) 的數據，\(N\leq 1000\)。
對于 \(100\%\) 的數據，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超過 \(10^9\)。
【分析】最大值最小，典型二分答案
二分左邊界 x, chk 當最大值 x 的時候是否合法
思考 是否需要 long long
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, a[N];
// 最大值 x 的情況下能否分出至多 m 段
bool chk(int x) {
int s = 0, t = 0;
for (int i = 1; i <= n; i++) {
if (t + a[i] < x) t += a[i];
else if (t + a[i] == x) t = 0, s++;
else t = a[i], s++;
}
if (t) s++;
return s <= m;
}
int main() {
int l = 1, r = 1e9, ans = r;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], l = max(l, a[i]);
while (l <= r) {
int mid = l + r >> 1;
chk(mid) ? r = mid - 1, ans = mid : l = mid + 1;
}
cout << ans << endl;
return 0;
}
P1032 [NOIP2002 提高組] 字串變換
已知有兩個字串 \(A,B\) 及一組字串變換的規則（至多 \(6\) 個規則），形如：
- \(A_1\to B_1\)。
- \(A_2\to B_2\)。
規則的含義為：在 \(A\) 中的子串 \(A_1\) 可以變換為 $ B_1\(，\)A_2$ 可以變換為 \(B_2\cdots\)。
輸入格式：第一行有兩個字符串 \(A,B\)。接下來若干行，每行有兩個字符串 \(A_i,B_i\)，表示一條變換規則。
輸出格式：若在 \(10\) 步（包含 \(10\) 步）以內能將 \(A\) 變換為 \(B\)，則輸出最少的變換步數；否則輸出 NO ANSWER!。
in:
abcd xyz
abc xu
ud y
y yz
out:
3
【數據規模與約定】
對于 \(100\%\) 數據，保證所有字符串長度的上限為 \(20\)。
【分析】最小步數，一眼bfs
題目主要在數據的處理上面有點難度，現在 x,y 是字符串類型，不好記錄 g[x][y]=1 的情況。
思考一下，可以使用 map<pair<string,string>, bool> mp;
問題解決， bfs 即可。
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
string A, B, a, b;
map<pair<string, string>, bool> mp;
map<string, int> st;
void bfs() {
queue<string> q;
q.push(A), st[A] = 1;
while (q.size()) {
auto u = q.front(); q.pop();
if (st[u] > 10) continue;
if (u == B) {
cout << st[u] - 1 << endl;
return;
}
for (auto it : mp) {
a = it.first.first, b = it.first.second;
int p = u.find(a);
while (p != -1) {
string v = u;
v.replace(v.begin() + p, v.begin() + p + a.size(), b);
if (!st[v]) st[v] = st[u] + 1, q.push(v);
p = u.find(a, p + a.size());
}
}
}
cout << "NO ANSWER!" << endl;
}
int main() {
cin >> A >> B;
while (cin >> a >> b) mp.insert({make_pair(a, b), 1});
bfs();
return 0;
}
P1020 [NOIP1999 提高組] 導彈攔截
某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度，計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
輸入格式：一行，若干個整數，中間由空格隔開。
輸出格式：兩行，每行一個整數，第一個數字表示這套系統最多能攔截多少導彈，第二個數字表示如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
in:
389 207 155 300 299 170 158 65
out:
6
2
【數據規模與約定】
對于前 \(50\%\) 數據（NOIP 原題數據），滿足導彈的個數不超過 \(10^4\) 個。該部分數據總分共 \(100\) 分。可使用\(\mathcal O(n^2)\) 做法通過。
對于后 \(50\%\) 的數據，滿足導彈的個數不超過 \(10^5\) 個。該部分數據總分也為 \(100\) 分。請使用 \(\mathcal O(n\log n)\) 做法通過。
對于全部數據，滿足導彈的高度為正整數，且不超過 \(5\times 10^4\)。
【分析】題目含有兩個問題
// v1 : 最長不上升子序列長度
// v2 : 需要多少導彈
解法1：DP，復雜度 \(O(n^2)\)
解法2：貪心+二分，復雜度 \(O(nlogn)\)
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n = 0, a[N], f[N], h[N];
// v1 : 最長下降子序列長度
// v2 : 需要多少導彈
namespace dp {
void solve() {
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] <= a[j]) f[i] = max(f[i], f[j] + 1);
ans1 = max(ans1, f[i]);
}
for (int i = 1; i <= n; i++) {
int k = 0;
while (k <= ans2 && h[k] < a[i]) k++;
h[k] = a[i];
if (k > ans2) ans2++;
}
cout << ans1 << endl << ans2 << endl;
}
}; // namespace dp
namespace binary_Search {
void solve() {
int ans1 = 0, ans2 = 0;
for (int i = n; i >= 1; i--) {
if (i == n || f[ans1 - 1] <= a[i]) f[ans1++] = a[i];
else *upper_bound(f, f + ans1, a[i]) = a[i];
}
for (int i = 1; i <= n; i++) {
int k = lower_bound(h + 1, h + 1 + ans2, a[i]) - h;
h[k] = a[i];
if (k > ans2) ans2++;
}
cout << ans1 << endl << ans2 << endl;
}
}; // namespace binary_Search
int main() {
while (cin >> a[++n]); n--;
// dp::solve();
binary_Search::solve();
return 0;
}
P1077 [NOIP2012 普及組] 擺花
小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共 \(m\) 盆。通過調查顧客的喜好，小明列出了顧客最喜歡的 \(n\) 種花，從 \(1\) 到 \(n\) 標號。為了在門口展出更多種花，規定第 \(i\) 種花不能超過 \(a_i\) 盆，擺花時同一種花放在一起，且不同種類的花需按標號的從小到大的順序依次擺列。
試編程計算，一共有多少種不同的擺花方案。
輸入格式：第一行包含兩個正整數 \(n\) 和 \(m\)，中間用一個空格隔開。第二行有 \(n\) 個整數，每兩個整數之間用一個空格隔開，依次表示 \(a_1,a_2, \cdots ,a_n\)。
輸出格式：一個整數，表示有多少種方案。注意：因為方案數可能很多，請輸出方案數對 \(10^6+7\) 取模的結果。
in:
2 4
3 2
out:
2
【數據范圍】
對于 \(20\%\) 數據，有 \(0<n \le 8,0<m \le 8,0 \le a_i \le 8\)。
對于 \(50\%\) 數據，有 \(0<n \le 20,0<m \le 20,0 \le a_i \le 20\)。
對于 \(100\%\) 數據，有 \(0<n \le 100,0<m \le 100,0 \le a_i \le 100\)。
【分析】
好好閱讀理解這句話的含義：擺花時同一種花放在一起，且不同種類的花需按標號的從小到大的順序依次擺列。
也就意味著，不需要考慮花的位置，只需要考慮數量；那么問題就很顯然，這是一個多重背包的裸題。
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, a[N], mod = 1e6 + 7;
namespace DP1 {
int dp[N][N]; // dp[i][j] 用前 i 種花擺 j 盆的方案數
void solve() {
for (int i = 0; i <= n; i++)
dp[i][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k <= a[i] && k <= j; k++) {
int& t = dp[i][j];
t = (t + dp[i - 1][j - k]) % mod;
}
cout << dp[n][m] << endl;
}
}; // namespace DP1
namespace DP2 {
int dp[N]; // dp[j] 擺 j 盆的方案數
void solve() {
dp[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--)
for (int k = 1; k <= a[i] && k <= j; k++) {
int& t = dp[j];
t = (t + dp[j - k]) % mod;
}
cout << dp[m] << endl;
}
}; // namespace DP2
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
DP1::solve();
DP2::solve();
return 0;
}
T264125 黑暗能量
有\(n\) 瓶裝有黑暗能量的容器，第 \(i\) 個容器里裝有質量為 \(a_i\) 的黑暗能量。
兩人盡可能多的平分黑暗能量，剩下無法平分的黑暗能量只能放棄使用。
【數據規模與約定】
本題共有 \(20\) 個測試點。
對于 \(50\%\) 的數據，\(n \le 13\)；
對于 \(70\%\) 的數據，\(n \le 50\)，提供的黑暗能量的總質量不超過 \(10^3\)；
對于 \(100\%\) 的數據，\(n \le 500\)，提供的黑暗能量的總質量不超過 \(10^5\)。
注意：對于以上三檔數據，每檔數據中分別含有 \(1\) 個測試點空間限制為 \(2\) MB，即總共有 \(15\%\) 的測試點空間限制為 \(2\) MB，其余測試點空間限制為 \(256\) MB。
【分析】
對于 \(50\%\) 的數據，\(n \le 13\)；--- 枚舉所有情況 \(3^{13}\)，很小
滿分解法，DP + 滾動數組優化，具體描述看代碼
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 501, INF = 0x3f3f3f3f;
int n, m, a[N];
// 枚舉 TLE：3^n ---- 012
void solve1() {
int ans = 0, tt = pow(3, n);
for (int i = 0; i < tt; i++) {
int t = i, p = n, b[3] = {0};
while (t) {
b[t % 3] += a[p--], t /= 3;
}
if (b[1] == b[2])
ans = max(ans, b[1]);
}
cout << 2 * ans << endl;
}
// dp[i][j][k] -- 前 i件物品，羊j 狼k 的情況是否存在
void solve2() {
bool dp[501][501][501];
memset(dp, 0x00, sizeof dp);
dp[0][0][0] = 1;
int p = 500;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
for (int k = 0; k <= p; k++) {
bool& t = dp[i][j][k];
t = dp[i - 1][j][k];
if (!t && j >= a[i])
t = dp[i - 1][j - a[i]][k];
if (!t && k >= a[i])
t = dp[i - 1][j][k - a[i]];
}
}
}
int ans = 0;
for (int i = 0; i <= p; i++)
ans = max(ans, dp[n][i][i] ? i : 0);
cout << 2 * ans << endl;
}
// dp[i][j] -- 前 i件物品，羊狼差距 j 的最大質量
void solve3() {
int dp[501][50001];
memset(dp, 0x80, sizeof dp);
dp[0][0] = 0;
int p = 50000;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
int& t = dp[i][j];
t = dp[i - 1][j];
if (j + a[i] <= p)
t = max(t, dp[i - 1][j + a[i]] + a[i]);
t = max(t, dp[i - 1][abs(j - a[i])] + a[i]);
}
}
cout << dp[n][0] << endl;
}
// dp[i][j] -- 前 i件物品，羊狼差距 j 的最大質量
void solve4() {
int dp[2][100001];
memset(dp, 0x80, sizeof dp);
dp[0][0] = 0;
int p = 50000;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p; j++) {
int& t = dp[i & 1][j];
t = dp[(i - 1) & 1][j];
if (j + a[i] <= p)
t = max(t, dp[(i - 1) & 1][j + a[i]] + a[i]);
t = max(t, dp[(i - 1) & 1][abs(j - a[i])] + a[i]);
}
}
cout << dp[n & 1][0] << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], m += a[i];
solve1();
solve2();
solve3();
solve4();
return 0;
}
貪心
P1090 [NOIP2004 提高組] 合并果子
\(n\) 堆果子經過 \(n-1\) 次合并后， 剩下一堆，把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。求最小消耗體力。
輸入格式：第一行是一個整數 n ，表示果子的種類數。
第二行包含 n個整數，第 i 個整數 \(a_i\) 是第 i 種果子的數目。
輸出格式：最小的體力耗費值。輸入數據保證這個值小于 \(2^{31}\)。
說明/提示：\(1 ≤ n ≤ 10000, 1 ≤ a_i ≤ 20000\)。
【分析】貪心策略：每次選擇最小的兩個元素進行合并。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int main() {
priority_queue<int, vector<int>, greater<int>> q;
int n, x, ans = 0; cin >> n;
for (int i = 1; i <= n; i++)
cin >> x, q.push(x);
while (q.size() > 1) {
auto a = q.top(); q.pop();
auto b = q.top(); q.pop();
q.push(a + b), ans += a + b;
}
cout << ans;
return 0;
}
P1803 凌亂的yyy / 線段覆蓋
有 \(n\) 個比賽，每個比賽的開始、結束的時間點是知道的，最多能參加幾個比賽。
如果要參加一個比賽必須善始善終，而且不能同時參加 \(2\) 個及以上的比賽。
輸入格式：第一行是一個整數 \(n\)，接下來 \(n\) 行每行是 \(2\) 個整數 \(a_{i},b_{i}\ (a_{i}<b_{i})\)，表示比賽開始、結束的時間。
輸出格式：一個整數最多參加的比賽數目。
數據范圍：對于 \(100\%\) 的數據，\(1\le n \le 10^{6}\)，\(0 \le a_{i} < b_{i} \le 10^6\)。
【分析】貪心策略：先結束的優先選擇。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
struct T {
int l, r;
bool operator<(const T& t) const { return r < t.r; }
} a[N];
int main() {
cin >> n;
for (int i = 1, l, r; i <= n; i++)
cin >> l >> r, a[i] = {l, r};
sort(a + 1, a + 1 + n);
int ed = 0, ans = 0;
for (int i = 1; i <= n; i++)
if (a[i].l >= ed) ans++, ed = a[i].r;
cout << ans << endl;
return 0;
}
P1190 [NOIP2010 普及組] 接水問題
有 \(m\) 個龍頭，\(n\) 名同學準備接水，他們的初始接水順序已經確定。將這些同學按接水順序從 \(1\) 到 \(n\) 編號，\(i\) 號同學的接水量為 \(w_i\)。接水開始時，\(1\) 到 \(m\) 號同學各占一個水龍頭，并同時打開水龍頭接水。當其中某名同學 \(j\) 完成其接水量要求 \(w_j\) 后，下一名排隊等候接水的同學 \(k\) 馬上接替 \(j\) 同學的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即 \(j\) 同學第 \(x\) 秒結束時完成接水，則 \(k\) 同學第 \(x+1\) 秒立刻開始接水。若當前接水人數 \(n'\) 不足 \(m\)，則只有 \(n'\) 個龍頭供水，其它 \(m - n'\) 個龍頭關閉。
現在給出 \(n\) 名同學的接水量，按照上述接水規則，問所有同學都接完水需要多少秒。
輸入格式：
第一行兩個整數 \(n\) 和 \(m\)，用一個空格隔開，分別表示接水人數和龍頭個數。
第二行 \(n\) 個整數 \(w_1,w_2,\ldots,w_n\)，每兩個整數之間用一個空格隔開，\(w_i\) 表示 \(i\) 號同學的接水量。
輸出格式：一個整數，表示接水所需的總時間。
【數據范圍】\(1 \le n \le {10}^4\)，\(1 \le m \le 100\)，\(m \le n\), \(1 \le w_i \le 100\)。
【分析】貪心策略：每次選擇當前最先完成的水龍頭打水。
使用 w[i] 記錄當前水龍頭的用時，每次用最小的打水，最后用時最大的就是答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, w[N], a[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = m + 1; i <= n; i++) {
sort(w + 1, w + 1 + m);
w[1] = w[1] + w[i];
}
sort(w + 1, w + 1 + m);
cout << w[m] << endl;
return 0;
}
P1106 刪數問題
鍵盤輸入一個高精度的正整數 \(n\)（不超過 \(250\) 位），去掉其中任意 \(k\) 個數字后剩下的數字按原左右次序將組成一個新的非負整數。編程對給定的 \(n\) 和 \(k\)，尋找一種方案使得剩下的數字組成的新數最小。
輸入格式：輸入兩行正整數。
第一行輸入一個高精度的正整數 \(n\)。
第二行輸入一個正整數 \(k\)，表示需要刪除的數字個數。
輸出格式：輸出一個整數，最后剩下的最小數。
數據范圍：用 \(\operatorname{len}(n)\) 表示 \(n\) 的位數，保證 \(1 \leq k < \operatorname{len}(n) \leq 250\)。
【分析】怎么才能維護最小的數，考慮一個單調遞增的數列即可
方法1：維護一個單調遞增棧，如果元素遞增時刪除的數量不足 k，那么刪除棧頂元素即可；最后去除前導0.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
char st[N]; // 遞增的元素
int hh, k;
string s;
int main() {
cin >> s >> k;
// 1. 構造升序序列 st --- 單調遞增棧
for (auto u : s) {
while (k && hh && st[hh] > u)
hh--, k--;
st[++hh] = u;
}
// 2. 倒著刪除 k 個字符
while (k)
hh--, k--;
// 3. 字符串結尾 '\0'
st[hh + 1] = '\0';
// 4. 去除前導 0
int x = 1;
while (x < hh && st[x] == '0')
x++;
// 5. 答案 st[x, hh]
cout << st + x;
return 0;
}
方法2：字符串模擬
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int main() {
string s; int k;
while (cin >> s >> k) {
while (k) {
bool flag = 1;
for (int i = 0; i < s.size(); i++)
if (s[i] > s[i + 1]) {
s.erase(i, 1), k--, flag = 0;
break;
}
// 前導 0
while (s.find('0') == 0 && s.size() > 1) s.erase(0, 1);
if (flag) break;
}
for (int i = s.size(); k && i > 1; i--)
s.erase(i, 1), k--;
cout << s << endl;
}
return 0;
}
P2878 [USACO07JAN] Protecting the Flowers S
有 \(n\) 頭奶牛跑到 FJ 的花園里去吃花兒了，它們分別在距離牛圈 \(T_i\)（這里指 FJ 到那里需要 \(T_i\) 分鐘) 處吃花，每分鐘會吃掉 \(D_i\) 朵花，FJ 現在要將它們給弄回牛圈，但是他每次只能弄一頭回去，來回用時總共為 \(2 \times T_i\) 分鐘，在這段時間內，其它的奶牛會繼續吃 FJ 的花，速度保持不變，當然正在被趕回牛圈的奶牛不能繼續吃了。現在求在最好的方案下奶牛吃掉花的最小朵數。
【分析】貪心策略：優先選擇趕回去代價小的。
假設對于牛 a,b 而言，如果
先趕牛 a，需要代價 \(2×a.t×b.d\)
先趕牛 b，需要代價 \(2×b.t×a.d\)
選擇先趕代價小的，所以\(2×a.t×b.d < 2×b.t×a.d\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
struct T {
int t, d;
bool operator<(const T& temp) const {
return 2 * t * temp.d < 2 * temp.t * d;
}
} t[N];
ll n, sum = 0, ans = 0;
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> t[i].t >> t[i].d;
for (int i = 0; i < n; i++)
sum += t[i].d;
sort(t, t + n);
for (int i = 0; i < n; i++) {
sum -= t[i].d;
ans += sum * 2 * t[i].t;
}
cout << ans;
return 0;
}
P4712 「生物」能量流動
生物課上，小 F 學習到了食物鏈、食物網的相關內容。
他學到，能量是逐級遞減的。比如在食物鏈上，兩個鏈接起來的生物 \(A \rightarrow B\)（意思是 \(B\) 吃 \(A\)）之間的能量傳遞效率最多只有 \(\frac 1 5\)；而研究種間關系，能夠使能量流向對人類最有益的部分。
現在，小 F 想研究一下能量流動的關系，于是他在腦海里創造了一個生態的系統。
在這個生態的系統里，有 \(n+2\) 種生物，其中 \(0\) 是生產者，整個生態系統所流經的能量由它固定；你是貪婪的頂級掠食者 \(n + 1\)，可以捕食所有生物；其他的掠食者 \([1, n]\) 各有各的喜好，只會捕食編號在 \([0, r_i]\) 的生物。由于天然形成的強弱順序，上述關系滿足 \(r_i \leq r_{i + 1}(1 \leq i < n),\) \(r_i < i(1 \leq i \leq n)\)。
每種動物需要攝取至少 \(a_i\) 單位能量才能存活；一個生物攝取到的能量可以傳遞給捕食者，但傳遞效率都不超過 \(\frac 1 5\)。也就是說，假設該動物捕獲了 \(b_i\) 單位的能量，所有捕食它的掠食者得到的能量總和 \(c_i\)，那么有：
- \(b_i \geq a_i\)
- \(c_i \leq \frac 1 5 b_i\)
你希望知道，在所有生物都存活的情況下，在最優情況下你能獲取到的最大能量是多少。
輸入格式：
輸入第一行兩個整數 \(n, a_0(1 \leq n \leq 10 ^ 5, 1 \leq a_0 \leq 10 ^ 9)\)。\(a_0\) 是生產者固定的能量值。
接下來 \(n\) 行，每行 \(2\) 個正整數，表示 \(a_i, r_i(1 \leq a_i \leq 10 ^ 9)\)。
數據保證，\(0\leq r_i < i, r_i \leq r_{i + 1}\)。
輸出格式：
輸出一行一個浮點數，表示你——頂級掠食者——能得到的最大能量。如果不能使得所有生物存活（包括你自己），請輸出 \(-1\)。
你的答案與參考答案的相對誤差或者絕對誤差不超過 \(10 ^ {-8}\) 即被認為是正確的。如果你的程序是正確的，可以不用考慮精度問題。
子任務 \(1(21 \mathrm{pts}) : n \leq 100\)；
子任務 \(2(89 \mathrm{pts}) : n \leq 10 ^ 5\)。
【分析】考慮都能活+頂級掠食者能得到最大的能量，那么前面的能活即可。
為避免浮點數誤差，可以求最小轉換前的能量 \(5×a_i\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, a[N], r[N];
int main() {
cin >> n >> a[0];
for (int i = 1; i <= n; i++)
cin >> a[i] >> r[i];
int now = 0, sum = a[0];
for (int i = 1; i <= n; i++) {
while (now < r[i]) sum += a[++now];
if (sum < 5 * a[i]) {
puts("-1"); return 0;
}
sum -= a[i] * 5;
}
while (now < n) sum += a[++now];
printf("%.9lf", sum * 0.2);
return 0;
}
浙公網安備 33010602011771號