找峰值点 从小到大输出

1 #include
      
        2 #include
       
         3 int a[50001],b[50001]; 4 int main() 5 { 6     int i,j,k,n,m; 7     while(scanf("%d", &n)!=EOF) 8     { 9         int g = 0;10         for(i = 1; i <= n ; i++)11             scanf("%d", &a[i]);12         if(n==1)13         {14             printf("1\n");15             continue;16         }17         if(a[1]>=a[2])18             b[g++] = 1;19         for(i = 2 ; i < n ; i++)20         {21             if(a[i-1]<=a[i]&&a[i]>=a[i+1])22                 b[g++] = i;23         }24         if(a[n]>=a[n-1])25             b[g++] = n;26         for(i = 0 ;i < g ; i++)27             printf("%d\n",b[i]);28     }29     return 0;30 }
       
      

并查集 注意是多组

1 #include
      
        2 #include
       
         3 #include
        
          4 struct node 5 { 6     int u,v; 7 }q[10011]; 8 int father[10011],r[10011],w[111][111]; 9 int find(int x)10 {11     if(x!=father[x])12         father[x] = find(father[x]);13     return father[x];14 }15 int main()16 {17     int n,m,k,i,j,a,b,g = 0;18     while(scanf("%d%d%d", &n,&m,&k)!=EOF)19     {20         memset(w,0,sizeof(w));21         g = 0;22         for(i = 1; i <= k ; i++)23         {24             father[i] = i;25             r[i] = 1;26         }27         for(i = 1; i <= k ; i++)28         {29             scanf("%d%d", &a,&b);30             if(w[a][b]==0&&a>=1&&a<=n&&b>=1&&b<=m)31             {32                 q[++g].u = a;33                 q[g].v = b;34                 w[a][b]  =1;35             }36         }37         for(i = 1; i < g ; i++)38         {39             for(j = i+1; j <= g ; j++)40             {41                 if((abs(q[i].u-q[j].u)==1&&q[i].v==q[j].v)||(q[i].u==q[j].u&&abs(q[i].v-q[j].v)==1))42                 {43                     int px = find(i);44                     int py = find(j);45                     if(px!=py)46                     {47                         father[px] = py;48                         r[py]+=r[px];49                     }50                 }51             }52         }53         int max = 0;54         for(i = 1; i <= g ; i++)55             if(max
        
       
      

记录每个1前面2的个数 和每个1后面1的个数 找min{d[i][1]+d[i][2]}

1 #include
      
        2 #include
       
         3 int a[30001],b[30001],d[30001][3]; 4 int main() 5 { 6     int i,j,k,n,m,min; 7     while(scanf("%d", &n)!=EOF) 8     { 9         memset(d,0,sizeof(d));10         min = 50000;11         int f = 0;12         for(i  =1; i <= n ; i++)13         {14             scanf("%d", &a[i]);15         }16         for(i = 1; i <= n ; i++)17         {18             if(a[i]==1)19                 d[i][2] = d[i-1][2];20             else21                 d[i][2] = d[i-1][2]+1;22         }23         for(i = n ; i >= 1; i--)24         {25             if(a[i]==2)26                 d[i][1] = d[i+1][1];27             else28                 d[i][1] = d[i+1][1]+1;29         }30         for(i = 1 ; i <= n ; i++)31         {32             if(a[i]==1)33             {34                 if(min>d[i][1]+d[i][2]-1)35                 min = d[i][1]+d[i][2]-1;36                 f = 1;37             }38         }39         if(!f)40             min = 0;41         printf("%d\n",min);42     }43     return 0;44 }
       
      

这题描述的太不清楚了 n值并不表示 最多就有n个点 从输入里面找一个最大值

因为走到头要返回 而只有最后一次走不用返回 所以最后走那一条最长的

最小生成树 求出和S 用S-生成树中最长的那一条

1 #include 
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 #define INF 100000000 6 int w[501][501],d[501],vis[501],dis[501]; 7 void prime(int n) 8 { 9     int i,j,k,s = 0;10     memset(vis,0,sizeof(vis));11     vis[0] = 1;12     for(i = 0; i <= n ; i++)13     {14         d[i] = w[0][i];15         if(w[0][i]!=INF)16         dis[i] = w[0][i];17         else18         dis[i]= 0;19     }20     for(i = 0; i <= n ;i++)21     {22         int min = INF;23         for(j = 0; j <= n ;j++)24         if(!vis[j]&&d[j]
         
          w[k][j])32         {33             d[j] = w[k][j];34             dis[j] = dis[k]+w[k][j];35         }36     }37     int mi = -1;38     for(i = 1; i <= n ; i++)39     {40 41         if(dis[i]>mi)42         mi = dis[i];43     }44     printf("%d\n",s*2-mi);45 }46 int main()47 {48     int i,j,k,n,m,a,b,c;49     while(scanf("%d", &n)!=EOF)50     {51        for(i = 0 ;i <= 100; i++)52        {53           for(j = 0 ; j <= 100; j++)54           w[i][j] = INF;55           w[i][i] = 0;56        }57         m = 0;58         for(i = 1; i <= n ; i++)59         {60             scanf("%d%d%d",&a,&b,&c);61             if(w[a][b]>c)62             {63                 w[a][b] = c;64                 w[b][a] = c;65             }66             if(a>m)67             m = a;68             if(b>m)69             m = b;70         }71         prime(m);72     }73     return 0;74 }