多米诺骨牌由上下 2 个方块组成,每个方块中有 1~6 个点。现有排成 行的上方块中点数之和记为 S1,下方块中点数之和记为 S2,它们的 差为|S1-S2|。如图,S1=6+1+1+1=9,S2=1+5+3+2=11,|S1-S2|=2。 每个多米诺骨牌可以旋转 180°,使得上下两个方块互换位置。请你 计算最少旋转多少次才能使多米诺骨牌上下 2 行点数之差达到最小。 对于图中的例子,只要将最后一个多米诺骨牌旋转 180°,即可使上 下 2 行点数之差为 0。 输入格式:输入文件的第一行是一个正整数 n(1<=n<= 1000),表示多米诺骨牌 数。接下来的 n 行表示 n 个多米诺骨牌的点数。每行有两个用空格隔开的正整数, 表示多米诺骨牌上下方块中的点数 a 和 b,且 1<= a,b<= 6。 输出格式:输出文件仅一行,包含一个整数。表示求得的最小旋转次数
时间: 2024-02-12 17:04:46 浏览: 51
这是一道简单的贪心算法题目。先计算出每个多米诺骨牌上下两个方块的点数之差 diff = |a-b|,然后将所有多米诺骨牌按照 diff 从小到大排序。接下来,我们需要将这些多米诺骨牌依次旋转180度,使得点数之差最小。
具体实现方法是,从 diff 最小的多米诺骨牌开始,如果上下两个方块的点数相等,不需要旋转;否则将这个多米诺骨牌旋转180度,使得较小的点数在上方,较大的点数在下方,这样可以使得点数之差更小。然后依次处理下一个 diff 更大的多米诺骨牌,直到所有多米诺骨牌都被处理完毕。
以下是参考代码:
```
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
struct Domino {
int a, b, diff;
} dominoes[N];
bool cmp(Domino &d1, Domino &d2) {
return d1.diff < d2.diff;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> dominoes[i].a >> dominoes[i].b;
dominoes[i].diff = abs(dominoes[i].a - dominoes[i].b);
}
sort(dominoes, dominoes + n, cmp);
int ans = 0;
for (int i = 0; i < n; i++) {
if (dominoes[i].a != dominoes[i].b) {
ans++;
if (dominoes[i].a > dominoes[i].b) swap(dominoes[i].a, dominoes[i].b);
}
}
cout << ans << endl;
return 0;
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)