商品关联次数统计

题目描述:

人们通过研究发现，将某些不同商品（比如休闲食品和饮料）陈列在一起销售，能使相关商品的销售量增长20%到30%（比如“啤酒和尿布”的故事）。为了寻找这些能相互促进销量的商品，就需要进行商品的关联分析。

为了统计相关商品的关联次数，需要对每个购物篮中的清单进行统计。

输入格式:

第一行，三个数，表示商品的种类n，购物篮的个数m，询问的次数T。

接下来，m行，每行包括若干商品的名称（商品名称都是字母x后跟一个整数），每两种商品名称之间用一个逗号隔开。

接下来，T行，每行两个整数x,y，表示询问x商品与y商品的关联次数。

输出格式:

每行一个数，表示根据询问，回答的相应次数。

样例输入:

9 3 4
x1,x2,x3,x4,x5,x6
x1,x4,x7,x8,x9
x2,x5,x6,x7,x9
1 4
5 6
7 8
3 8

样例输出:

2
2
1
0

提示:

n<=500，m<=2000, T<=100

来源高中教材必修1的P69。

算法提示：

对每个购物蓝分析：该购物篮中的商品，两两之间有一次关联。

请完善下面的程序：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 510;
int a[N][N], b[N], x, y, n, m, T;
string s, s0;
int main() {
	cin >> n >> m >> T;
	for ( int i=1; i<=m; i++ ){
		cin >> s;  //读入一行以逗号隔开的商品名，如：x1,x7,x12,x5
		s = s + ',';
		int p = s.find( ','), t = 0;
		while ( p != -1 ){
			s0 = s.substr( 1, p );     //反复找逗号，并把逗号之前的一个商品名提取出来，但x这个字符不要
			b[ ++t ] = atoi( s0.c_str() );  // atoi( ) 函数是把c语言风格的字符串，转成整数
			s.erase( 0, p +1 );
			p = s.find( ',');
		}
		//登记每个篮子中两两商品的关联
		_____________________________
	}
	for ( int i=1; i<=T; i++ ){
		cin >> x >> y;
		cout << a[x][y] << '\n';
	}
	return 0;
}

时间限制: 10000ms
空间限制: 512MB

---

来源: 原创