建设网站 知乎,中国住房与城乡建设厅网站,网站推广公司就去柚米,元器件采购最好的网站这题我们数据范围太大#xff0c;用二维肯定是不行的#xff0c;我们可以采用一维线性存储。
如题意#xff0c;我们可以将每组奶牛编号都存在一维数组里面#xff0c;只需记录每组的头尾指针就可以了。
如题中样例我们就可以存储成1 3 3 4 1 2 3 4 5 6 7 4 3 2 1
然后第…这题我们数据范围太大用二维肯定是不行的我们可以采用一维线性存储。
如题意我们可以将每组奶牛编号都存在一维数组里面只需记录每组的头尾指针就可以了。
如题中样例我们就可以存储成1 3 3 4 1 2 3 4 5 6 7 4 3 2 1
然后第一组头尾指针就是 1,2 。
第二组头尾指针就是3,4。
第二组头尾指针就是 5,11。
第二组头尾指针就是12,15。
#includeiostream
using namespace std;
const int N 1e6 10;
pairint, int q[N]; //q用于记录每组的头和尾
int e[N], d[N]; //d用于记录每组的数量e用于将所有组的奶牛线性存储
int n, g, ans;
bool f[N]; //用于判断当前编号是否被邀请过
bool fz[N];//用于判断每组是否都邀请过
int main()
{cin n g;int idx 0;for(int i1;ig;i){cin d[i];for (int j 1; j d[i]; j){cin e[idx]; //将所有组奶牛线性存储}//存储每组的头尾指针//如例题e中存入的是1 3 3 4 1 2 3 4 5 6 4 3 2 1//第一组是1 3那么q[1]的头尾指针就对应1 3下标也就是12int head idx - d[i] 1; int tail idx;q[i] { head,idx };}f[1] true;int mm 0;do{mm 0;for (int i 1; i g; i){int hh q[i].first;int tt q[i].second;int c 0; //当前组邀请的人数int flag 0; //记录没被邀请人的下标for (int j hh; j tt; j){if (f[e[j]]) //如果当前编号已经被邀请了当前组邀请的人数c;elseflag j;}if (c d[i] - 1){f[e[flag]] true; //邀请前组唯一一个没被邀请的人fz[i] true; //现在当前组就全部被邀请了mm 1; //既然已经新邀请了一个人那么就要判断是否还要再继续邀请}if (c d[i]) //如果相等就说明改组已经全部邀请fz[i] true;}} while (mm 1); //如果mm1才说明需要进一步邀请否则就不需要邀请了for (int i 1; i n; i)if (f[i])ans; //如果被邀请数量就1cout ans endl;return 0;
}
算法小白的刷题日记.
