【刷题记录】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),问最少需要交换几次?数据保证合法。

【刷题记录】GCJ 2.71~2.72

【输入样例(第一行为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;
}
上一篇:C++中的向上类型转换和向下类型转换


下一篇:和textrank4ZH代码一模一样的算法详细解读