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;
}