1 条题解

  • 0
    @ 2025-5-22 19:55:39

    题意分析​

    本题给定了三个关键参数:考普莱特牛群中牛的数量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
    上传者