ACM/ICPC 2010 杭州现场赛 National Day Parade 题解
这是在 Greenmoon55′s Blog 挖掘出来的水题一则。果断凑数。
思路是把每行的学生的列坐标分别排序，枚举左边一列的列号即可。
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <cmath> #include <cstdio> #include <climits> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 222; int i2j[N][N], cnt[N], n, m, n2; int main() { // freopen("input.txt", "r", stdin); while (cin >> n >> m) { if (n == 0 && m == 0) break; memset(cnt, 0, sizeof cnt); n2 = n * n; for (int i = 0; i < n2; ++i) { int k, a; cin >> k; --k; cin >> a; --a; i2j[k][cnt[k]++] = a; } for (int i = 0; i < n; ++i) sort(i2j[i], i2j[i] + n); int rmost = m - n, sum, result = INT_MAX; for (int i = 0; i <= rmost; ++i) { sum = 0; for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) sum += abs(i2j[j][k] - (i + k)); result = min(result, sum); } cout << result << endl; } return 0; } |
