【刷题记录】GCJ 2.71~2.72
GCJ 271
【题目大意】
Minimum Scalar Product
有两个东西（滑稽）v1=（x1,x2,x3,……,xn）和v2=（y1,y2,……yn），允许任意交换v1和v2中各数字的顺序。
请计算x1y1+……+xnyn的最小值
【输入样例（第一行为n，第二行为v1，第三行为v2）】
3 1 3 -5 -2 4 1
【输出样例（直接输出最小值）】
-25
【数据范围】
稍微大一点的：100<=n<=800 -100000<=x1,y1<=100000
【解题思路】
直接暴力sort一下v1和v2，最后计算v1[i]*v2[n-i-1]即可
【代码】
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=801;
int n;
int v1[maxn],v2[maxn];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>v1[i];
for(int i=0;i<n;i++) cin>>v2[i];
sort(v1,v1+n);
sort(v2,v2+n);
ll ans=0;
for(int i=0;i<n;i++) ans+=(ll)v1[i]*v2[n-i-1];
cout<<ans<<endl;
return 0;
}
GCJ 272
【题目大意】
Crazy Rows（2009 Round2 A题）（滑稽）
给定一个由0和1组成的矩阵。只允许交换相邻的两行（第i行和第i+1行），要把矩阵化成下三角矩阵（主对角线上方的元素都为0），问最少需要交换几次？数据保证合法。
【输入样例（第一行为n代表有一个n*n的矩阵，下面n行为矩阵）】
4 1110 1100 1100 1000
【输出样例（直接输出代价）】
4
【数据范围】
稍微大一点的：4<=n<=40
【解题思路】
N！肯定不行
我们就先把第一行确定，第一行必须是“1000000……000”或“00000……0000”的形式。所以我们把矩阵中符合这种形式的行中代价较小的放到第一行。
下一行像处理第一行一样处理，现在复杂度为O（n^3）
接着，我们预先计算最终矩阵每行最后一个1所在的位置即可，现在复杂度变成了n方……
【代码】
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int n;
char a[50];
int b[50];
bool used[50];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
b[i]=-1;
used[i]=false;
cin>>a;
for(int j=n-1;j>=0;j--)
{
if(a[j]=='1')
{
b[i]=j;
break;
}
}
}
int s=0;
for(int i=0;i<n;i++)
{
int ans=-1;
for(int j=i;j<n;j++)
{
if(b[j]<=i)
{
ans=j;
break;
}
}
for(int j=ans;j>i;j--)
{
swap(b[j],b[j-1]);
s++;
}
}
cout<<s;
return 0;
}