当前位置：首页 > ds >正文

算法设计课作业

ds 2025/7/5 7:38:41

实验一

POJ 3970 最小公倍数

题目描述

给定 $N$ 个正整数（ $\leq N \leq 20$ ），计算这些数的最小公倍数（LCM）。若结果大于或等于 $10^6$ ，输出 Too much money to pay!，否则输出 The CEO must bring X pounds.，其中 $X$ 为最小公倍数。

输入

多组测试用例，每组用例：
- 一行以整数 $N$ 开头，后跟 $N$ 个正整数（均不超过 $10^6$ ）。
- 输入以 $N = 0$ 结束。

输出
对每个用例，按题意输出结果。

样例输入

2 12 4
1 3000000
0

示例输出

The CEO must bring 12 pounds.
Too much money to pay!

答案

#include <iostream>
using namespace std;
//最大公约数
int gcd(int da, int xiao)
{return xiao ? gcd(xiao, da % xiao) : da;
}
//最小公倍数
int lcm(int x,int y){int t = x*y;return t/gcd(x,y);
}int main(){int n;while(cin>>n){if(n == 0) break;int ans = 1;while(n--){int x;cin>>x;ans = lcm(x,ans);}if(ans < 1000000){cout<<"The CEO must bring " <<ans<< " pounds."<<endl;}else {cout<<"Too much money to pay!"<<endl;}}return 0;
}

POJ 3487 稳定婚姻问题

题目描述

给定 $n$ 个男性和 $n$ 个女性的偏好列表（每个男性对女性排名，每个女性对男性排名），求稳定婚姻匹配。稳定匹配定义：不存在一对男女，他们彼此喜欢对方的程度超过当前的配偶。

输入

第一行为测试用例数 $T$ 。
每个用例：
- 第一行为整数 $n$ （ $\leq 26$ ）。
- 接下来 $n$ 行，每行描述一个男性的偏好列表（如 a:ABCD 表示男性 a 的偏好顺序为 A > B > C > D）。
- 再接下来 $n$ 行，每行描述一个女性的偏好列表（如 A:abcd 表示女性 A 的偏好顺序为 a > b > c > d）。

输出
对每个用例，按字母顺序输出每个男性的配偶（每行格式如 a A）。

样例输入

1
4
a:ABCD
b:ABCD
c:ABCD
d:ABCD
A:dcba
B:dcba
C:dcba
D:dcba

示例输出

a D
b C
c B
d A

答案

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
int main() {int x;cin >> x;bool first = true;while (x--) {if (!first) cout << endl;first = false;int n;cin >> n;vector<char> male_names(n), female_names(n);for (int i = 0; i < n; ++i) cin >> male_names[i];//输入男性名字for (int i = 0; i < n; ++i) cin >> female_names[i];//输入女性名字//男性名字 女性名字 映射序号map<char, int>male_map, female_map;for (int i = 0; i < n; i++) {male_map[male_names[i]] = i;//'a' -> 0female_map[female_names[i]] = i;//'A' -> 0}//=====男性偏好索引列表=====vector<vector<int> > male_prefs(n); //存储偏好索引for(int i = 0; i<n; i++) {string line;cin >> line;//此行对应的男性名称char c = line[0];//喜欢的那几个提取出来string line_male_prefs = line.substr(2);int male_index = male_map[c];//当前行的男性序号for (int j = 0; j < line_male_prefs.size(); ++j) {  // 修改为传统循环char x = line_male_prefs[j];int female_index = female_map[x];//当前男性喜欢的每个女性的序号male_prefs[male_index].push_back(female_index);}}//=====女性偏好索引列表====vector<vector<int> > female_prefs(n); //同上vector<vector<int> > female_rank(n, vector<int>(n)); //存储女性对男性的排名for (int i = 0; i < n; i++) {string line ;cin >> line;//此行对应的女性名字char c = line[0];//提取喜欢的人的序号string line_female_prefs = line.substr(2);int female_index = female_map[c];//当前行的女性序号for (int j = 0; j < line_female_prefs.size(); ++j) {  // 修改为传统循环char x = line_female_prefs[j];int male_index = male_map[x];//当前行女性喜欢的男性的序号的映射female_prefs[female_index].push_back(male_index);//喜欢的每个女性push进去}//反向数组 存储女性对男性的喜欢程度排名，用于下面的配偶调换for (int j = 0; j < n; j++) {int m = female_prefs[female_index][j];female_rank[female_index][m] = j;}}//=====输入的数据处理完毕=====/*a:BACb:BACc:ACBA:acbB:bacC:cab则male_prefs为   [[1 0 2],[1 0 2],[0 2 1]]female_prefs为 [[0 2 1],[1 0 2],[2 0 1]]frmale_prefs[0][2] = 10号女第(2+1)喜欢的男性是1号男==>female_rank[0][1] = 2;0号女对1号男的喜欢顺序是第(2+1)*///=====开始GS算法========vector<int> wife(n, -1); // wife[m] = 男性m当前匹配的女性索引vector<int> husband(n, -1); // husband[f] = 女性f当前匹配的男性索引stack<int> q; // 存储当前单身的男性for (int i = 0; i < n; i++) q.push(i); // 初始所有男性入栈while (!q.empty()) {int cur_index = q.top();//当前未婚配男性q.pop();//如果当前男性没有配偶,对于喜欢列表的女性依次匹配for (int k = 0; k < male_prefs[cur_index].size(); ++k) {  // 修改为传统循环int p = male_prefs[cur_index][k];if (wife[cur_index] != -1) break; // 已匹配则跳过if (husband[p] == -1) {husband[p] = cur_index;//男性找到配偶wife[cur_index] = p;//女性找到配偶break;//退出循环} else if (husband[p] != -1) { //当前女性有配偶int this_woman_husband = husband[p];//p对cur_index对应的男的喜欢程度比原配更大，则换//这是排名 越小越喜欢if (female_rank[p][cur_index] < female_rank[p][this_woman_husband]) {//当前匹配成功husband[p] = cur_index;wife[cur_index] = p;//原配偶变为单身wife[this_woman_husband] = -1;//入单身栈q.push(this_woman_husband);break;} else {//p对cur_index喜欢程度更小continue;}}}}//========== 按字典序输出结果 ==========vector<char> sorted_males = male_names;sort(sorted_males.begin(), sorted_males.end()); // 按字母顺序排序for (int i = 0; i < sorted_males.size(); ++i) {  // 修改为传统循环char c = sorted_males[i];int m = male_map[c];         // 获取男性索引int f = wife[m];             // 获取匹配的女性索引cout << c << " " << female_names[f] << endl;}}return 0;
}

实验二

人们各不相同。有些人偷偷地阅读满是迷人女孩图片的杂志，有些人在自家地窖里制造原子弹，有些人喜欢使用 Windows 系统，还有些人喜欢有难度的数学游戏。最新的市场调研显示，到目前为止，这一细分市场被低估了，并且缺乏这类游戏。因此，这类游戏被纳入了 KOKODáKH 中。规则如下：
每位玩家选择两个数字 $A_i$ 和 $B_i$ ，并将它们写在一张纸条上。其他人看不到这些数字。在某个特定时刻，所有玩家向其他人展示自己的数字。目标是计算包括自己在内的所有玩家的所有表达式 $A_i^{B_i}$ 的总和，然后计算该总和除以给定数字 M 后的余数。最先得出正确结果的玩家获胜。根据玩家的经验，通过选择更大的数字可以增加游戏的难度。
你需要编写一个程序，计算出结果，并能够找出谁赢得了游戏。
输入
输入由 Z 组任务组成。任务的数量由输入第一行出现的单个正整数 Z 给出。然后是各个任务。每个任务以包含一个整数 M（ $\leq M \leq 45000$ ）的行开始。总和将除以这个数字。接下来一行包含玩家数量 H（ $\leq H \leq 45000$ ）。紧接着恰好有 H 行。在每一行上，恰好有两个用空格分隔的数字 $A_i$ 和 $B_i$ 。这两个数字不能同时为零。
输出
对于每个任务，只有一行输出。在这一行上，有一个数字，即表达式 $(A_1^{B_1}+A_2^{B_2}+ \cdots +A_H^{B_H})\bmod M$ 的结果。
输入样例

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

输出样例

2
13195
13

答案

#include<iostream>
using namespace std;
//快速幂要求每次做乘法，都要取余
//3^10 = (9)^5 = (3^2)^5
//而9^5 = 9 * 9^4 = 9*(81)^2 = 9*(9^2)^2
//由此可见，b是奇数是要分成a*a^(b-1)的形式
//就是多乘个此时的a(a也是不断乘方的)
long long fastPowMod(long long a,long long b,long long m){//(a^b)%mif(m == 1) return 0;//任何数模1均为0long long res = 1;a = a%m;while(b){if(b&1) res = (res * a)%m;a = (a*a)%m;b >>= 1;}return res;
}
int main(){int N;int M;cin>>N;//N组数while(N--){long long sum = 0;cin>>M;//对M取余int p;cin>>p;//几对数while(p--){int A,B;cin>>A>>B;sum += fastPowMod(A,B,M);sum%=M;}cout<<sum<<endl;}return 0;
}

POJ2092（计数排序）

题目描述

全家人都为这个消息感到兴奋。大家都知道爷爷几十年来一直是个非常出色的桥牌玩家，但当宣布他将被载入《吉尼斯世界纪录》，成为有史以来最成功的桥牌玩家时，哇，那可太令人惊讶了！
国际桥牌协会（IBA）多年来一直在维护一份世界最佳桥牌玩家的每周排名。考虑到每次出现在每周排名中都会为玩家积一分，爷爷因为获得了最高的积分而被提名为有史以来最优秀的玩家。
爷爷有很多也是他竞争对手的朋友，他非常好奇想知道哪些玩家获得了第二名。由于现在 IBA 的排名可以在互联网上查到，他便向你求助。他需要一个程序，当给定一系列每周排名时，能根据积分找出获得第二名的玩家（或玩家们）。
输入
输入包含多个测试用例。玩家由从 1 到 10000 的整数来标识。每个测试用例的第一行包含两个整数 N 和 M，分别表示可用的排名数量（2 <= N <= 500）和每个排名中的玩家数量（2 <= M <= 500）。接下来的 N 行，每行都包含一个每周排名的描述。每个描述都由 M 个整数组成的序列构成，这些整数之间用一个空格分隔，标识出在该周排名中出现的玩家。你可以假设：

在每个测试用例中，恰好有一名最佳玩家，并且至少有一名次佳玩家。
每个每周排名都由 M 个不同的玩家标识组成。
当 N = M = 0 时，表示输入结束。
输出

对于输入中的每个测试用例，你的程序必须输出一行内容，包含在排名中出现次数位居第二的玩家的标识号。如果存在并列第二名的情况，则按升序输出所有并列第二名玩家的标识号。输出的每个标识号后面都必须跟一个空格。
输入样例

4 5
20 33 25 32 99
32 86 99 25 10
20 99 10 33 86
19 33 74 99 32
3 6
2 34 67 36 79 93
100 38 21 76 91 85
32 23 85 31 88 1
0 0

输出样例

32 33
1 2 21 23 31 32 34 36 38 67 76 79 88 91 93 100

答案

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, m;while (cin >> n >> m) {if (n == 0 && m == 0) break;vector<int> counter(10001, 0); // 玩家ID范围是1~10000int most = 0;   // 最高出现次数int sec_most = 0; // 次高出现次数// 统计出现次数for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {int x;cin >> x;counter[x]++;most = max(most, counter[x]);}}// 计算次高出现次数for (int i = 1; i <= 10000; ++i) {if (counter[i] != most) {sec_most = max(sec_most, counter[i]);}}// 收集结果并排序vector<int> ans;for (int i = 1; i <= 10000; ++i) {if (counter[i] == sec_most) {ans.push_back(i);}}// 输出结果for (size_t k = 0; k < ans.size(); ++k) {cout << ans[k] << " ";}cout << endl;}return 0;
}

POJ2503（快速查找）

题目描述

你刚刚从滑铁卢搬到了一座大城市。这里的人说着一种让人难以理解的外语方言。幸运的是，你有一本字典可以帮助你理解他们的话。
输入
输入包含最多 100,000 条字典词条，然后是一个空行，接着是一条最多包含 100,000 个单词的信息。每个字典词条是一行，包含一个英语单词，后面跟着一个空格和一个外语单词。在字典中，任何一个外语单词都不会出现超过一次。这条信息是由一些外语单词组成的序列，每个单词占一行。输入中的每个单词都是由最多 10 个小写字母组成的序列。
输出
输出是翻译成英语后的信息，每个单词占一行。字典中没有的外语单词应该翻译成 “eh”。
输入样例

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslayatcay
ittenkay
oopslay

输出样例

cat
eh
loops

提示
输入和输出数据量巨大，建议使用 scanf 和 printf。

答案

#include <iostream>
#include <string>
#include <map> // 替换unordered_map为map，并包含对应头文件
using namespace std;map<string, string> dic; // 使用map替代unordered_mapint main() {ios::sync_with_stdio(0);cin.tie(0);string line;while (getline(cin, line)) {if (line.empty()) break;//找出分割号‘ ’的位置size_t space = line.find(' ');//提取英语string eng = line.substr(0, space);//提取本地语string foreign = line.substr(space + 1);//pair<string,string>赋值dic[foreign] = eng;}string word;while (cin >> word) {//直接查找输出if (dic.count(word)) cout << dic[word] << "\n";else cout << "eh\n";}return 0
}

实验三

POJ 3061 尺取法/滑动窗口

题目描述

给出了 N 个正整数序列（ $10 < N < 100000$ ），每个正整数都小于或等于 10000，以及一个正整数 S （ $S < 100000000$ ）。编写一个程序来查找序列的连续元素的子序列的最小长度，其总和大于或等于 S。
输入

第一行是测试用例的数量。
对于每个测试用例：
- 程序必须从第一行读取数字 N 和 S，用间隔分隔。
- 序列的编号在测试用例的第二行中给出，以间隔分隔。
输入将以文件结尾结束。
输出
对于每种情况，程序必须在输出文件的单独行上打印结果，如果没有答案，则打印 0。
样本输入

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

示例输出

2
3

答案

#include <iostream>
#include <vector>
using namespace std;int main() {int m;cin >> m;while (m--) {int N, S;cin >> N >> S;vector<int> nums(N);for (int i = 0; i < N; ++i) {cin >> nums[i];}int left = 0, sum = 0, min_len = N + 1;for (int right = 0; right < N; ++right) {sum += nums[right];while (sum >= S) {min_len = min(min_len, right - left + 1);sum -= nums[left++];}}cout << (min_len <= N ? min_len : 0) << endl;}return 0;
}

POJ 2785 折半+枚举

题目描述

给定四个元素个数相同的整数集合 $A, B, C, D$ （每个集合元素个数 $\leq 4000$ ），计算有多少个四元组 $(a, b, c, d)$ 满足 $a + b + c + d = 0$ ，其中 $\in A, b \in B, c \in C, d \in D$ 。

输入

第一行包含整数 $N$ ，表示每个集合的元素个数。
接下来的 $N$ 行，每行四个整数，分别表示 $A, B, C, D$ 中的元素。所有元素的绝对值不超过 $2^{28}$ 。

输出
输出满足条件的四元组数量。

样例输入

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

示例输出

四列分左右两部分
根据左部分二分的对右部分查找
$O (log_2n)$

答案

#include <bits/stdc++.h>
using namespace std;
int n ;
int main(){cin>>n;//每列多少数字vector<int>A(n),B(n),C(n),D(n);for(int i = 0;i<n;i++){cin>>A[i]>>B[i]>>C[i]>>D[i];//输入每组数的第i个数}//A B 和 C Dint t = 0;vector<int>a(n*n);//存放A+Bvector<int>b(n*n);//存放C+Dfor(int i = 0;i<n;i++){for(int j= 0;j<n;j++){a[t] = A[i] + B[j];b[t] = C[i] + D[j];//各自相加t++;}}//a b 排序sort(b.begin(),b.end());//二分匹配int res = 0;for(int i = 0;i<a.size();i++){const int target = -a[i];//下界vector<int>::iterator left = lower_bound(b.begin(),b.end(),target);//上界vector<int>::iterator right = upper_bound(b.begin(),b.end(),target);res += (right - left);}cout<<res;return 0;
}

POJ 3977 折半+枚举

题目描述

给定一个包含 $N$ 个整数的集合（ $\leq N \leq 35$ ），选择一个非空子集，使得子集元素和的绝对值最小。若存在多个解，选择元素个数最少的那个。输出最小绝对值及对应子集的大小。

输入

多组测试用例，每组用例：
- 第一行为整数 $N$ 。
- 第二行包含 $N$ 个整数，用空格分隔。每个数的绝对值不超过 $10^{15}$ 。
输入以 $N = 0$ 结束。

输出
对于每个用例，输出最小绝对值和子集大小，用空格分隔。

样例输入

1
10
3
20 100 -100
0

示例输出

10 1
0 2

答案

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;typedef long long ll;
const ll INF_LL = 0x3f3f3f3f3f3f3f3fLL;struct CompareFirst {bool operator()(const pair<ll, int>& a, const pair<ll, int>& b) const {return a.first < b.first;}
};void generate_sums(const vector<ll>& a, vector<pair<ll, int> >& sums) {sums.clear();int n = a.size();vector<pair<ll, int> > temp;for (int mask = 1; mask < (1 << n); ++mask) {ll sum = 0;int cnt = 0;for (int i = 0; i < n; ++i) {if (mask & (1 << i)) {sum += a[i];++cnt;}}temp.push_back(make_pair(sum, cnt));}sort(temp.begin(), temp.end(), CompareFirst());if (temp.empty()) return;ll current = temp[0].first;int min_cnt = temp[0].second;for (size_t i = 1; i < temp.size(); ++i) {if (temp[i].first == current) {if (temp[i].second < min_cnt) min_cnt = temp[i].second;} else {sums.push_back(make_pair(current, min_cnt));current = temp[i].first;min_cnt = temp[i].second;}}sums.push_back(make_pair(current, min_cnt));
}int main() {int n;while (cin >> n && n != 0) {vector<ll> nums(n);for (int i = 0; i < n; ++i) cin >> nums[i];int k = n / 2;vector<ll> a(nums.begin(), nums.begin() + k);vector<ll> b(nums.begin() + k, nums.end());vector<pair<ll, int> > a_sums, b_sums;generate_sums(a, a_sums);generate_sums(b, b_sums);ll min_abs = INF_LL;int min_cnt = n + 1;// 处理a的子集for (size_t i = 0; i < a_sums.size(); ++i) {ll s = a_sums[i].first;int c = a_sums[i].second;ll abs_s = (s >= 0) ? s : -s;  // 替换llabsif (abs_s < min_abs || (abs_s == min_abs && c < min_cnt)) {min_abs = abs_s;min_cnt = c;}}// 处理b的子集for (size_t i = 0; i < b_sums.size(); ++i) {ll s = b_sums[i].first;int c = b_sums[i].second;ll abs_s = (s >= 0) ? s : -s;  // 替换llabsif (abs_s < min_abs || (abs_s == min_abs && c < min_cnt)) {min_abs = abs_s;min_cnt = c;}}// 合并处理CompareFirst comp;for (size_t i = 0; i < a_sums.size(); ++i) {ll s_a = a_sums[i].first;int c_a = a_sums[i].second;pair<ll, int> target = make_pair(-s_a, 0);vector<pair<ll, int> >::iterator it = lower_bound(b_sums.begin(), b_sums.end(), target, comp);// 检查后一个元素if (it != b_sums.end()) {ll total = s_a + it->first;ll abs_total = (total >= 0) ? total : -total;  // 替换llabsint cnt = c_a + it->second;if (abs_total < min_abs || (abs_total == min_abs && cnt < min_cnt)) {min_abs = abs_total;min_cnt = cnt;}}// 检查前一个元素if (it != b_sums.begin()) {--it;ll total = s_a + it->first;ll abs_total = (total >= 0) ? total : -total;  // 替换llabsint cnt = c_a + it->second;if (abs_total < min_abs || (abs_total == min_abs && cnt < min_cnt)) {min_abs = abs_total;min_cnt = cnt;}}}cout << min_abs << " " << min_cnt << endl;}return 0;
}

POJ 2549 折半+枚举

题目描述

给定一个包含 $N$ 个不同整数的集合 $S$ （ $\leq N \leq 1000$ ），找出不同的四个元素 $\in S$ ，满足 $a + b + c = d$ 。若存在多个解，输出最大的 $d$ ；否则输出 no solution。

输入

多组测试用例，每组用例：
- 第一行为整数 $N$ 。
- 第二行包含 $N$ 个不同的整数，用空格分隔。
输入以 $N = 0$ 结束。

输出
对于每个用例，输出满足条件的最大 $d$ 或 no solution。

样例输入

5
2 3 5 7 12
5
2 16 64 256 1024
0

示例输出

12
no solution

POJ 1256 排列

题目描述

给定一个字符串 $S$ ，包含大小写字母，生成所有可能的排列并按特殊字典序输出。字典序规则为：‘A’<‘a’<‘B’<‘b’<…<‘Z’<‘z’。

输入

第一行为测试用例数量 $T$ 。
每个用例一行，包含字符串 $S$ （长度 $\leq 13$ ）。

输出
对每个用例，按字典序输出所有排列，每个排列占一行。

样例输入

3  
aAb  
abc  
acba

示例输出

Aab  
Aba 
aAb  
abA  
bAa  
baA  
abc  
acb  
bac  
bca  
cab  
cba  
aabc  
aacb  
abac  
abca  
acab  
acba  
baac  
baca  
bcaa  
caab  
caba  
cbaa

答案

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;// 自定义比较函数，实现题目要求的字典序
bool compare(char a, char b) {// 先将字母转换为统一的比较形式char lowerA = tolower(a);char lowerB = tolower(b);if (lowerA == lowerB) {// 如果小写字母相同，大写字母在前return a < b;}// 否则按小写字母的字典序比较return lowerA < lowerB;
}void generate_permutation(string s) {// 使用自定义比较函数进行排序sort(s.begin(), s.end(), compare);do {// 处理当前排列（如输出、统计、条件判断）cout << s << endl;} while (next_permutation(s.begin(), s.end(), compare));
}int main() {int T;cin >> T;while (T--) {string s;cin >> s;generate_permutation(s);}return 0;
}

实验四（一）

POJ 3262 (贪心)

在运输奶牛的过程中，为了使被破坏花朵的总数最小，需要合理安排运输奶牛的顺序，这里的最小化是基于每头奶牛在等待运输时每分钟破坏花朵的数量以及将其运输到牛棚所需的时间。

题目描述

农夫约翰像往常一样去砍一些木头，留下了 N（ $\leq N \leq 100,000$ ）头奶牛在吃草。当他回来时，他惊恐地发现这群奶牛在他的花园里吃他美丽的花朵。为了尽量减少随后的损失，约翰决定立即采取行动，将每头奶牛送回它自己的牛棚。
每头奶牛 i 所在的位置距离它自己的牛棚需要 $T_i$ 分钟（ $\leq T_i \leq 2,000,000$ ）。此外，在等待运输的过程中，它每分钟会破坏 $D_i$ （ $\leq D_i \leq 100$ ）朵花。无论约翰多么努力，他一次只能运送一头奶牛回牛棚。将奶牛 i 运送到它的牛棚需要 $\times T_i$ 分钟（ $T_i$ 去牛棚的时间和 $T_i$ 返回的时间）。约翰从花丛处出发，将奶牛运送到牛棚，然后走回花丛处，去接下一头需要运输的奶牛时不额外花费时间。
输入
第 1 行：一个整数 N 第 2 行到 $N + 1$ 行：每行包含两个用空格分隔的整数 $T_i$ 和 $D_i$ ，描述了一头奶牛的特征
输出

第 1 行：一个整数，即被破坏花朵的最小数量
输入样例

输出样例

提示
约翰按照以下顺序送回奶牛：6, 2, 3, 4, 1, 5。当他运送奶牛 6 去牛棚时，其他奶牛破坏了 24 朵花；接下来他运送奶牛 2，又损失了 28 朵他美丽的花朵。对于奶牛 3、4、1，他分别损失了 16、12 和 6 朵花。当他接奶牛 5 时，没有其他奶牛再破坏花朵了，所以这头奶牛造成的损失为零。这样总共损失的花朵数量是 $24 + 28 + 16 + 12 + 6 = 86$ 。

答案

#include <iostream>
#include <vector>
#include <algorithm>// 定义奶牛结构体
struct Cow {int time;  // 回棚时间int damageRate;  // 破坏速度
};using LL = long long;int main() {int n;std::cin >> n;std::vector<Cow> cows(n);LL totalTime = 0;LL totalDamageRate = 0;// 输入每头奶牛的回棚时间和破坏速度for (int i = 0; i < n; ++i) {std::cin >> cows[i].time >> cows[i].damageRate;totalTime += cows[i].time;totalDamageRate += cows[i].damageRate;}// 按照 t/d 升序排序std::sort(cows.begin(), cows.end(), [](const Cow& a, const Cow& b) {return a.time * b.damageRate < a.damageRate * b.time;});// 计算总破坏量LL totalDamage = 0;for (int i = 0; i < n - 1; ++i) {totalDamageRate -= cows[i].damageRate;// 牵当前牛的过程中的破坏量totalDamage += 2 * totalDamageRate * cows[i].time;}std::cout << totalDamage;return 0;
}

在交换相邻奶牛 i 和 j 的顺序时，破坏量的差值计算中涉及其他奶牛（设为集合 S）的破坏项会相互抵消，具体推导如下：

推导过程
设其他奶牛的破坏速率总和为 $\sum_{k \in S} D_k$ ，则：
原顺序（i→j）的总破坏量

运输 i 时：
破坏源：j + 其他奶牛 → $D_j + S$ 。

时间： $2 T_i$ 。
破坏量： $(D_j + S) \cdot 2 T_i$ 。

运输 j 时：
破坏源：仅其他奶牛 → $S$ 。

时间： $2 T_j$ 。
破坏量： $\cdot 2 T_j$ 。

总破坏增量：
$\Delta_{\text{原}} = 2 T_i (D_j + S) + 2 T_j S$

新顺序（j→i）的总破坏量

运输 j 时：

破坏源：i + 其他奶牛 → $D_i + S$
时间： $2 T_j$
破坏量： $(D_i + S) \cdot 2 T_j$

运输 i 时：

破坏源：仅其他奶牛 → $S$ 。
时间： $2 T_i$ 。
破坏量： $\cdot 2 T_i$ 。
总破坏增量：
$\Delta_{\text{新}} = 2 T_j (D_i + S) + 2 T_i S$

计算差值
$\Delta_{\text{原}} - \Delta_{\text{新}} = \left[ 2 T_i (D_j + S) + 2 T_j S \right] - \left[ 2 T_j (D_i + S) + 2 T_i S \right]$

展开后：
$\underbrace{2 T_i D_j + 2 T_i S + 2 T_j S}_{\text{原顺序}} - \underbrace{2 T_j D_i + 2 T_j S + 2 T_i S}_{\text{新顺序}}$
关键观察：

$2 T_i S$ 和 $2 T_i S$ 相互抵消。
$2 T_j S$ 和 $2 T_j S$ 相互抵消。
剩余项：
$\Delta_{\text{原}} - \Delta_{\text{新}} = 2 T_i D_j - 2 T_j D_i$

结论
所有与 其他奶牛破坏速率（ $S$ ） 相关的项在差值计算中完全抵消，最终结果仅取决于 i 和 j 的参数：
$\Delta_{\text{原}} - \Delta_{\text{新}} = 2 (T_i D_j - T_j D_i)$

这一结果表明：

若 $T_i D_j > T_j D_i$ ，交换顺序后破坏量减少，说明原解不是最优。
最优解必须满足 $T_i D_j \leq T_j D_i$ ，即按此条件排序。

POJ 3268 (最短路)

题目描述

有N个农场（ $\leq N \leq 1000$ ），农场编号为1到N，每一个农场都有一头奶牛。这些奶牛要去参加在农场X（ $\leq X \leq N$ ）举办的大型奶牛聚会。总共有M（ $\leq M \leq 100,000$ ）条单向道路连接着各个农场对；第i条道路需要 $T_i$ （ $\leq T_i \leq 100$ ）个时间单位来通过。
每头奶牛都必须走到聚会地点，并且聚会结束后还要回到自己的农场。每头奶牛都很懒，所以会选择用时最短的最优路线。由于道路是单向的，奶牛返回的路线可能与去聚会时的路线不同。
在所有奶牛中，一头奶牛往返聚会地点所花费的最长时间是多少呢？
输入

第 1 行：三个用空格分隔的整数，分别是：N，M和X 第 2 行到第 $M + 1$ 行：第 $i + 1$ 行用三个用空格分隔的整数 $A_i$ ， $B_i$ 和 $T_i$ 描述第i条道路。所描述的道路是从农场 $A_i$ 到农场 $B_i$ ，通过这条道路需要 $T_i$ 个时间单位。
输出
第 1 行：一个整数，表示一头奶牛必须行走的最长时间。
样例输入

示例输出

提示
奶牛4直接前往聚会地点（用时3个单位），然后经过农场1和农场3返回（用时7个单位），总共用时10个时间单位。

答案

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;typedef long long ll;
const int MAX_N = 1005;
const ll INF = 1e18;vector<pair<int, ll> > G[MAX_N]; // C++98需在>间加空格
vector<pair<int, ll> > R[MAX_N]; // 
ll d1[MAX_N], d2[MAX_N];
//最短路 Dijkstra算法
//单源最短路:一个点到另一个集合中所有点
struct Compare { // 自定义比较器替代greater<>bool operator()(const pair<ll, int>& a, const pair<ll, int>& b) {return a.first > b.first;}
};void dijkstra(vector<pair<int, ll> > g[], int start, ll d[]) { // 使用最小堆，存储<距离, 节点>，按距离升序排列priority_queue<pair<ll, int>, vector<pair<ll, int> >, Compare> pq;fill(d, d + MAX_N, INF);//初始化距离为最大d[start] = 0;//到自身距离为0pq.push(make_pair(0, start));while (!pq.empty()) {pair<ll, int> cur = pq.top();//选出来距离最小的pq.pop();ll dist = cur.first;int u = cur.second;if (dist > d[u]) continue;for (vector<pair<int, ll> >::iterator it = g[u].begin(); it != g[u].end(); ++it) { // C++98迭代器//与u点相邻的所有点及其距离//u -> v 距离为wint v = it->first;ll w = it->second;if (d[v] > d[u] + w) {d[v] = d[u] + w;pq.push(make_pair(d[v], v)); // 使用push代替emplace}}}
}int main() {int n, m, x;cin >> n >> m >> x;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;G[u].push_back(make_pair(v, w)); // 正向建图R[v].push_back(make_pair(u, w)); // 反向建图}dijkstra(G, x, d1);dijkstra(R, x, d2);ll max_time = 0;for (int i = 1; i <= n; ++i) {if (d1[i] != INF && d2[i] != INF)max_time = max(max_time, d1[i] + d2[i]);}cout << max_time << endl;return 0;
}//dijkstra算法是单源最短路问题
//是一个点x到一个集合s之间的最短距离
//所以写一个dijkstra的函数即可
//反向的x  -> v0 正常做
//正向的 v0 -> x 转化为将所有单向边反过来之后的x -> v0
//结果一样