1 条题解
-
0
题意分析
本题给定了三个关键参数:考普莱特牛群中牛的数量N、围栏柱子数量P以及允许的最大牛数量C。并且给出了每头牛所在的位置(具体为相邻两个柱子之间)。核心任务是在围栏的P - 1个柱子间隔中,找到一个连续的区间,使得该区间内包含的考普莱特牛数量不超过C头,同时这个区间的长度要尽可能大,区间长度指的是柱子之间的间隔数 。
解题思路
初始化数据结构:创建一个长度为P - 1的数组grazing来记录每个间隔是否有牛在吃草,初始化为 0。遍历输入的每头牛的位置信息,将对应间隔的grazing数组元素加 1,表示该间隔有牛在吃草。
滑动窗口法求解:
定义两个指针left和right,初始都指向数组grazing的起始位置,即left = right = 0,同时定义变量count用于记录当前窗口内牛的数量,初始化为 0,定义maxLength用于记录满足条件的最大区间长度,初始化为 0。不断移动right指针,将right指针指向的间隔的牛数量加到count中。
当count > C时,说明当前窗口内牛的数量超过了限制,此时需要移动left指针,将left指针指向的间隔的牛数量从count中减去,并将left指针右移一位,缩小窗口范围,直到count <= C。 在每次移动指针的过程中,更新maxLength为当前窗口长度(right - left + 1)和maxLength中的较大 值。
返回结果:遍历结束后,maxLength即为包含至多C头考普莱特牛的最大连续区域的大小,将其返回。
代码
#include<iostream> #include<math.h> using namespace std; bool visit[10000]; typedef struct enode{ int adj; struct enode *next; }enode; typedef struct vnode{ enode *find; }vnode; typedef vnode List[10000]; typedef struct graphic{ List list; int n,e; }graphic; typedef struct Edge{ int s, e; } Edge; Edge E[100000]; int order[10000],id[10000],in[10000]; int cnt; void create(graphic *g,graphic *g1){ scanf("%d %d",&g->n,&g->e); g1->n=g->n; g1->e=g->e; for(int i=0;i<g->n;i++){ g->list[i].find=NULL; g1->list[i].find=NULL; } for(int i=0;i<g->e;i++){ enode *p=(enode *)malloc(sizeof(enode)); int k,m; scanf("%d%d",&k,&m); k--; m--; E[i].s=k; E[i].e=m; p->adj=m; p->next=g->list[k].find; g->list[k].find=p; p=(enode *)malloc(sizeof(enode)); p->adj=k; p->next=g1->list[m].find; g1->list[m].find=p; } } void dfs1(graphic *g,int i){ enode *p=g->list[i].find;; visit[i]=true; while(p) { if(!visit[p->adj]) dfs1(g,p->adj); p=p->next; } order[cnt++]=i; } void dfs(graphic *g,int i){ enode *p=g->list[i].find;; visit[i]=true; id[i]=cnt; while(p) { if(!visit[p->adj])dfs(g,p->adj); p=p->next; } } void dfs2(graphic *g,int i){ enode *p=g->list[i].find; visit[i]=true; while(p){ if(id[i]!=id[p->adj]) in[i]++; if(!visit[p->adj]) dfs(g,p->adj); p=p->next; } } int main(){ int pos; graphic *g=(graphic *)malloc(sizeof(graphic)); graphic *g1=(graphic *)malloc(sizeof(graphic)); create(g,g1); memset(visit,0,sizeof(visit)); cnt=0; for(int i=0;i<g->n;i++) if(!visit[i]) dfs1(g1,i); memset(visit,0,sizeof(visit)); cnt=0; for(int i=g->n-1;i>=0;i--){ if(!visit[order[i]]){ dfs(g,order[i]); cnt++; } } int s,e; for (int i = 0; i < g->e; i++){ //一个部落能通往其他部落则为1 s = id[E[i].s]; e = id[E[i].e]; if (s != e) in[s]++; } int scnt = cnt; cnt = 0; for(int i = 0; i < scnt; i++){ //如果强连通则只有一个为0 if (in[i] == 0){ pos = i; //保存了最后的那个部落 cnt++; } } if (cnt != 1) printf("0\n"); else{ cnt = 0; for (int i = 0; i < g->n; i++) if (in[id[i]] == pos) //求出最后那个部落的人数 cnt++; printf("%d\n", cnt); } system("pause"); return 0; } ``` ```
- 1
信息
- ID
- 1190
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者