时间限制: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