GCJ 2009 Round2 A 构造贪心策略

分类：ACM_贪心

题意: 给你一个的元素只为0或1的矩阵，要把该矩阵通过行交换变为上三角矩阵，且交换方式只能为相邻行交换。问最小的交换步数是多少？

思路：首先这个行的利用价值就是最右边的1位置是多少，直接把行抽象为最右边1的数字即可。注意：这里WA了一发，没有注意数字要初始化为0。无论多么简单，写完之后检查代码且保证逻辑没有一丝错误十分重要！这个题主要的是构造贪心的法则：题中只需要满足第一行的数字小于1，第二行的数字小于2，…..,第n行的数字小于n。那么就从第一行开始，一行一行的来看，注意若当前行的数组小于等于行数就，到下一行，如果不满足，就需要在底下行中挑选距离该行最近，且满足条件的数字交换上来。仔细思考这个策略，会发现，它很好的做到了不会出现矛盾的交换，和每步最优思想。

Code：

;int main(void) {//freopen(“A-small-practice.in”, “r”, stdin);freopen(“A-large-practice.in”, “r”, stdin);freopen(“a.txt”, “w”, stdout);int t, n, a[50];scanf(“%d”, &t);for (int l = 1; l <= t; l++) {scanf(“%d”, &n);for (int i = 0; i < n ; i++) {a[i + 1] = 0;string s;cin >> s;for (int j = n – 1; j >= 0; j–) {if (s[j] != ‘0’) {a[i + 1] = j + 1;break;}}}int ans = 0;for (int i = 1; i <= n; i++) {if (a[i] <= i) continue;for (int j = i + 1; j <= n; j++) {if (a[j] <= i) {for (int k = j; k > i; k–) {swap(a[k], a[k – 1]);ans++;}break;}}}printf(“Case #%d: %d\n”, l, ans);}return 0;}

上一篇GCJ 2008 Round 1A A 排序贪心下一篇《深入理解计算机系统》第一章读书笔记

顶0踩0

有人要进来，有一些人不得不离开。

相关文章：

你感兴趣的文章：

标签云：