题目连接:

  http://poj.org/problem?id=2947

题目大意:

  有n种类型的零件,m个工人,每个零件的加工时间是[3,9],每个工人在一个特定的时间段内可以生产k个零件(可以相同种类,也可以不同种类),问每种零件生产一个出来需要的时间?

解题思路:

  给出的时间段是从周几到周几,并没有给出具体的时间段,因此在计算过程中要进行取模,还有就是对每个零件要在题目要求的范围内进行枚举。

ps:如果求出来的增广矩阵是n*n的,但是某个零件在[3,9]之间没有合理的解,也是无解的。

 #include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = ;
int det[maxn][maxn], res[maxn], var, equ;
char str[][] = {"","MON", "TUE", "WED", "THU", "FRI", "SAT" , "SUN"};
int Day (char s[])
{
for (int i=; i<; i++)
if (strcmp(s, str[i]) == )
return i;
}
int gauss ()
{
int col, k;
for (k=col=; k<equ&&col<var; k++, col++)
{
int Max_i = k;
for (int i=k+; i<equ; i++)
if (abs(det[i][col]) > abs(det[Max_i][col]))
Max_i = i;
if (Max_i != k)
for (int i=col; i<=var; i++)
swap (det[k][i], det[Max_i][i]);
if (det[k][col] == )
{
k --;
continue;
}
for (int i=k+; i<equ; i++)
if (det[i][col])
{
int x = det[i][col];
int y = det[k][col];
for (int j=col; j<=var; j++)
det[i][j] = ((det[i][j]*y - det[k][j]*x) % + ) % ;
}
}
int temp = , i, j;
for (i=; i<equ; i++)
{
for (j=; j<var; j++)
if (det[i][j])
break;
if (j == var)
{
if (det[i][j])
return ;//增广矩阵无解
else if (i < var)//增广矩阵存在不确定变元
temp ++;
}
}
if (temp || var > equ)
return ;//增广矩阵存在不确定变元 for (i=var-; i>=; i--)
{
temp = ;
for (j=i+; j<var; j++)
temp = (temp + det[i][j] * res[j]) % ;
for (j=; j<; j++)//枚举每个零件的加工时长
if ((temp + det[i][i]*j)% == det[i][var])
{
res[i] = j;
break;
}
if (j == )//当有某个零件的加工时长不在[3,9]之间,则不符合题意,无解
return ;
}
return ;
}
int main ()
{
while (scanf ("%d %d", &var, &equ), var+equ)
{
int k, x;
char st[maxn], et[maxn];
memset (det, , sizeof(det));
for (int i=; i<equ; i++)
{
scanf ("%d %s %s", &k, st, et);
while (k --)
{
scanf ("%d", &x);
det[i][x-] ++;
}
det[i][var] = Day(et) - Day(st) + ;
}
for (int i=; i<equ; i++)//这里一定要去次余,如果det[i][j]是7的倍数,在划成阶梯阵的过程中很有可能会错
for (int j=; j<=var; j++)
det[i][j] = (det[i][j] % + ) % ;
int ans = gauss();
if (ans == )
printf ("Inconsistent data.\n");
else if (ans == )
printf ("Multiple solutions.\n");
else
for (int i=; i<var; i++)
printf ("%d%c", res[i], i==var-?'\n':' ');
}
return ;
}

最新文章

  1. 【Excel】Excel根据单元格背景色求和
  2. ch6 影响 MySQLServer 性能的相关因素
  3. 清除 WD MyCloud 自动生成的 .wdmc 目录
  4. PHP程序员函数注释规格(麻烦大家遵守)
  5. Android布局_相对布局RelativeLayout
  6. 记录android5.0更新踩过的坑
  7. zend studio 9.0.4 安装破解
  8. angularJS 服务二
  9. 查看Oracle最耗时的SQL
  10. rsyslog安装
  11. Windows Phone 如果你把Pivot控件当成主页面,那么这篇文章你值得看。
  12. ajax入门之建立XHR对象 (1)
  13. Q:记学习枚举过程中的一个小问题
  14. 关于Android SDK Manager更新速度慢的解决方法
  15. [题解] P2513 [HAOI2009]逆序对数列
  16. 反素数ant HYSBZ - 1053(数学+dfs)
  17. 在线预览-Java 使用 Print2Flash 实现Office文档在线阅读
  18. python random使用方法
  19. Codeforces Round #538 (Div. 2)
  20. TypeScript 之 书写.d.ts文件

热门文章

  1. Java反射常用示例
  2. Failed to execute &#39;toDataURL&#39; on &#39;HTMLCanvasElement,在canvas.toDataURL()执行时候报错解决方案
  3. curl -s 不输出统计信息
  4. Java知识图谱
  5. [Tools] Create a Chrome Extension
  6. SQL2012 尝试读取或写入受保护的内存。这通常指示其它内存已损坏
  7. NYOJ 158 省赛来了
  8. excel 学习
  9. lsblk df
  10. h5ai目录列表优化