CodeForces 441A Valera and Antique Items

Note

In the first sample Valera can bargain with each of the sellers. He can outbid the following items: a 40000 item from the first seller, a 20000 item from the second seller, and a 10000 item from the third seller.

In the second sample Valera can not make a deal with any of the sellers, as the prices of all items in the auction too big for him.

大意——有n个古董卖家，第i个卖家有ki个古董要拍卖。当前知道第i个卖家的第j件古董的拍卖价格为sij，一个人和n个卖家的关系都比较好，他非常确定只要他出价高于第i个卖家的古董之一的当前价格，第i个卖家就会和他达成协议。但不幸的是，当前他仅仅只有v单位的钱了，问：他当前能和几个卖家达成协议，分别是哪几个(卖家按照标号呈上升序列给出)？

思路——简单模拟一下即可。将当前钱数与第i个卖家的所有古董拍卖价格进行比较，一旦发现当前钱数大于古董拍卖价格的情况，就记录可以和该卖家达成协议了，然后用一个数组记录卖家信息，数组下标表示卖家个数，数组元素表示卖家标号。最后和所有卖家古董拍卖价格都比较完了，直接输出最大数组下标，然后按顺序输出记录卖家标号的数组元素即可。

复杂度分析——时间复杂度:O(nk),空间复杂度:O(cnt)

附上AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef unsigned int li;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
short n, k;
int extra, value;int main()
{ios::sync_with_stdio(false);while (~scanf("%hd%d", &n, &extra)){short num[55], cnt=0;for (short i=0; i<n; i++){scanf("%hd", &k);bool flag = false;while (k--){scanf("%d", &value);if (extra > value)flag = true;}if (flag)num[cnt++] = i+1;}printf("%hd\n", cnt);for (short i=0; i<cnt; i++)printf("%d ", num[i]);printf("\n");}return 0;
}