首页 > 代码库 > [NOIP2013]火柴排队
[NOIP2013]火柴排队
题目描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑(ai-bi)^2, i=1~n，其中ai表示第一列火柴中第i个火柴的高度，bi表示第二列火柴中第i个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
输入格式
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出格式
输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。
样例输入
样例输出
样例输入
样例输出
注释
对于 10%的数据， 1 ≤ n ≤ 10；
对于 30%的数据，1 ≤ n ≤ 100；
对于 60%的数据，1 ≤ n ≤ 1,000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ 2^31-1
[分析]
根据题意，两列火柴的总距离就等于$$\sum{a^2| + \sum{b^2| - 2 * \sum{a_i * b_i}$$
对于一个给定的序列，前两项均为常数，于是我们的目标就转为最大化所有对应的$a_i * b_i$之和。
这里需要一个结论：\[ \\ \quad \quad \quad \forall a_1 \leq a_2, b_1 \leq b_2\,\in\, \mathbb{R} ，
\quad a_1*b_1 + a_2*b_2 \geq a_1*b_2 + a_2 * b_1 \]
人生苦短，这个简单的结论我们就不证了~ 2333333（好吧其实直接把不等式两边减一下再因式分解就好）
那么我们只需要把在对应序列中名次相同的两项匹配起来就好了……
于是我们就固定A不动(因为对A或B操作在对“两个同名次的项在两序列中的相对位置"的影响上是等价的)，把B中每个元素都与A中对应名次的元素对齐。不难发现，$$\forall i \le j \in [1, n]，若order_i \ge order_j，则i与j至少有一次交换. 那么最少的交换次数就等于order序列中的逆序对个数>_< 又是经典模型，随便套个算法就搞定了= =
对于一个给定的序列，前两项均为常数，于是我们的目标就转为最大化所有对应的$a_i * b_i$之和。
这里需要一个结论：\[ \\ \quad \quad \quad \forall a_1 \leq a_2, b_1 \leq b_2\,\in\, \mathbb{R} ，
\quad a_1*b_1 + a_2*b_2 \geq a_1*b_2 + a_2 * b_1 \]
人生苦短，这个简单的结论我们就不证了~ 2333333（好吧其实直接把不等式两边减一下再因式分解就好）
那么我们只需要把在对应序列中名次相同的两项匹配起来就好了……
于是我们就固定A不动(因为对A或B操作在对“两个同名次的项在两序列中的相对位置"的影响上是等价的)，把B中每个元素都与A中对应名次的元素对齐。不难发现，$$\forall i \le j \in [1, n]，若order_i \ge order_j，则i与j至少有一次交换. 那么最少的交换次数就等于order序列中的逆序对个数>_< 又是经典模型，随便套个算法就搞定了= =
1 #include <cstdio>
2 #include <cctype>
3 #include <algorithm>
4 #include <cstring>
5 #include <queue>
6 #include <cmath>
7
8 #if defined DEBUG
9 FILE *in = fopen("temp", "r");
10 #define out stdout
11 #else
12 FILE *in = fopen("MatchNOIP2013.in", "r");
13 FILE *out = fopen("MatchNOIP2013.out", "w");
14 #endif
15
16 inline void getint(int &x){
17 char c = fgetc(in);
18 while(!isdigit(c))c = fgetc(in);
19 x = c - ‘0‘;
20 while(isdigit(c = fgetc(in)))x = x * 10 - ‘0‘ + c;
21 }
22 typedef long long LL;
23 using namespace std;
24 inline int lowbit(int x){return x & -x;}
25 /*=====================================*/
26 const int maxn = 100000 + 5, mod = 99999997;
27 int n, A[maxn], B[maxn], t1[maxn], t2[maxn], ans = 0;
28
29 inline bool tmpa(int a, int b){return A[a] < A[b];}
30 inline bool tmpb(int a, int b){return B[a] < B[b];}
31
32 //namespace Fenwick{
33 int Arr[maxn] = {0};
34 inline void insert(int x){
35 ++Arr[x];
36 int i = x + lowbit(x);
37 while(i <= n){
38 ++Arr[i];
39 i += lowbit(i);
40 }
41 }
42 inline int getS(int x){
43 int ans = Arr[x], i = x ^ lowbit(x);
44 while(i){
45 ans += Arr[i];
46 i ^= lowbit(i);
47 }
48 return ans;
49 }
50 //}//Fenwick
51 //using Fenwick::getS;
52 //using Fenwick::insert;
53
54 inline void work(){
55 getint(n);
56 int i, ord[maxn];
57 for(i = 1;i <= n;++i)
58 getint(A[i]), t1[i] = i;
59 for(i = 1;i <= n;++i)
60 getint(B[i]), t2[i] = i;
61 sort(t1 + 1, t1 + n + 1, tmpa);
62 sort(t2 + 1, t2 + n + 1, tmpb);
63 for(i = 1;i <= n;++i)
64 ord[t1[i]] = t2[i];
65 for(i = n;i;--i){
66 ans = (ans + getS(ord[i])) % mod;
67 insert(ord[i]);
68 }
69 fprintf(out, "%d\n", (ans + mod) % mod);
70 }
71
72 int main(){
73
74 work();
75
76 return 0;
77 }
2 #include <cctype>
3 #include <algorithm>
4 #include <cstring>
5 #include <queue>
6 #include <cmath>
7
8 #if defined DEBUG
9 FILE *in = fopen("temp", "r");
10 #define out stdout
11 #else
12 FILE *in = fopen("MatchNOIP2013.in", "r");
13 FILE *out = fopen("MatchNOIP2013.out", "w");
14 #endif
15
16 inline void getint(int &x){
17 char c = fgetc(in);
18 while(!isdigit(c))c = fgetc(in);
19 x = c - ‘0‘;
20 while(isdigit(c = fgetc(in)))x = x * 10 - ‘0‘ + c;
21 }
22 typedef long long LL;
23 using namespace std;
24 inline int lowbit(int x){return x & -x;}
25 /*=====================================*/
26 const int maxn = 100000 + 5, mod = 99999997;
27 int n, A[maxn], B[maxn], t1[maxn], t2[maxn], ans = 0;
28
29 inline bool tmpa(int a, int b){return A[a] < A[b];}
30 inline bool tmpb(int a, int b){return B[a] < B[b];}
31
32 //namespace Fenwick{
33 int Arr[maxn] = {0};
34 inline void insert(int x){
35 ++Arr[x];
36 int i = x + lowbit(x);
37 while(i <= n){
38 ++Arr[i];
39 i += lowbit(i);
40 }
41 }
42 inline int getS(int x){
43 int ans = Arr[x], i = x ^ lowbit(x);
44 while(i){
45 ans += Arr[i];
46 i ^= lowbit(i);
47 }
48 return ans;
49 }
50 //}//Fenwick
51 //using Fenwick::getS;
52 //using Fenwick::insert;
53
54 inline void work(){
55 getint(n);
56 int i, ord[maxn];
57 for(i = 1;i <= n;++i)
58 getint(A[i]), t1[i] = i;
59 for(i = 1;i <= n;++i)
60 getint(B[i]), t2[i] = i;
61 sort(t1 + 1, t1 + n + 1, tmpa);
62 sort(t2 + 1, t2 + n + 1, tmpb);
63 for(i = 1;i <= n;++i)
64 ord[t1[i]] = t2[i];
65 for(i = n;i;--i){
66 ans = (ans + getS(ord[i])) % mod;
67 insert(ord[i]);
68 }
69 fprintf(out, "%d\n", (ans + mod) % mod);
70 }
71
72 int main(){
73
74 work();
75
76 return 0;
77 }
[NOIP2013]火柴排队
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。