hihoCoder 1195 高斯消元.一

传送门

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Ho:喂不得了啦,那边便利店的薯片半价了!

小Hi:啥?!

小Ho:那边的便利店在打折促销啊。

小Hi:走走走,赶紧去看看=v=

于是小Hi和小Ho来到了便利店。

老板为了促销,推出了组合包的形式,将不同数量的各类商品打包成一个组合,顾客可以选择组合进行购买。比如2袋薯片,1听可乐的组合只要5元,而1袋薯片,2听可乐的组合只要4元。

通过询问老板,小Hi和小Ho知道:一共有N种不同的商品和M种不同的商品组合;每一个组合的价格等于组合内商品售价之和,一个组合内同一件商品不会超过10件。

小Hi:这样算下来的话,一听可乐就是1元,而一包薯片是2元。小Ho,如果你知道所有的组合情况,你能分别算出每一件商品单独的价格么?

小Ho:当然可以了,这样的小问题怎么能难到我呢?

提示:高斯消元

输入

第1行:2个正整数,N,M。表示商品的数量N,组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行:N+1个非负整数,第i+1行第j列表示在第i个组合中,商品j的数量a[i][j]。第i+1行第N+1个数表示该组合的售价c[i]。0≤a[i][j]≤10, 0≤c[i]≤10^9

输出

若没有办法计算出每个商品单独的价格,输出"No solutions"

若可能存在多个不同的结果,输出"Many solutions"

若存在唯一可能的结果,输出N行,每行一个非负整数,第i行表示第i个商品单独的售价。数据保证如果存在唯一解,那么解一定恰好是非负整数解。

样例输入

2 2
2 1 5
1 2 4
样例输出
2
1

先贴代码
#include <bits/stdc++.h>
using namespace std;
const int N(), M();
const double EPS=1e-;
typedef double mat[M][N];
typedef double vec[N];
void swap(mat a, int i, int j){
vec tmp;
memcpy(tmp, a[i], sizeof(tmp));
memcpy(a[i], a[j], sizeof(tmp));
memcpy(a[j], tmp, sizeof(tmp));
}
//m>=n
int gauss(mat a, int n, int m){
int res=;
for(int i=; i<n; i++){
int pivot=i;
for(int j=i; j<m; j++)
if(abs(a[j][i])>abs(a[pivot][i]))
pivot=j;
swap(a, i, pivot);
// cout<<a[i][i]<<endl;
if(abs(a[i][i])<EPS){
res=-;
continue;
}
for(int j=i+; j<=n; j++) //ERROR-PRONE
a[i][j]/=a[i][i];
for(int j=; j<m; j++)
if(i!=j){
for(int k=i+; k<=n; k++) //ERROR-PRONE
a[j][k]-=a[j][i]*a[i][k];
}
}
for(int i=; i<n; i++){
if(abs(a[i][i])<EPS&&abs(a[i][n])>EPS){
res=;
break;
}
}
for(int i=n; i<m; i++)
if(abs(a[i][n])>EPS){
res=;
break;
}
return res;
}
int main(){
int n, m;
cin>>n>>m;
mat a;
for(int i=; i<m; i++)
for(int j=; j<=n; j++)
cin>>a[i][j];
int res=gauss(a, n, m);
if(!res)
puts("No solutions");
else if(!~res)
puts("Many solutions");
else
for(int i=; i<n; i++)
cout<<(int)(a[i][n]+0.5)<<endl;
}
这题有一个小坑:若结果中的某一项为0,由于增广矩阵为double类型,该项在实际结果中可能是一个绝对值很小的负数(比如-0.0001),此时如果用printf("%.0f"),将输出"-0"。由于这题输出为整数,就不会有对精度的特判,如此输出必然返
WA
办法是将结果加0.5再强制转换成int输出

这里强调一下printf("%.0f")和printf("%d",(int)())的区别
前者是按 “( 符号不变,绝对值 )四舍五入”( “四舍五入”确切地说是“小数部分>0.5则入,否则舍” )输出,后者是将浮点数往(数轴上)零的方向截断后输出。

比如
double res=0.5;
printf("%d %.0f\n", (int)res, res);

输出 0 0

double res=0.51;
printf("%d %.0f\n", (int)res, res);

输出 0 1

double res=-0.5;
printf("%d %.0f\n", (int)res, res);

输出 0 -0

double res=-0.51;
printf("%d %.0f\n", (int)res, res);

输出 0 -1

上一篇:hiho #1196 : 高斯消元·二


下一篇:laravel打印sql语句