• C++ 两个算法题目

    //解题思路：
    // 游标=0
    //先从头取第一次递增长度，结果值也等于此次长度
    // 进入循环
    // 游标 +=上次长度，如果游标==数组长度，退出循环
    //取游标位置递增长度
    //取的长度>=结果值，则结果值=取的长度+1
    //本次取的长度如果能与上次增长长度拼接且大于结果值，则结果值=拼接值
    //记录当前值
    //游标不到最后继续循环
    //最后输出结果值



    YZF 有一个序列 A，由 n 个整数组成。

    我们将子段 A 称为 Ai、Ai +1、Ai+ 2、…Aj（1<=i<=j=n）表示 A 的子段。

    你的任务是找到 A 的最长的子段，这样就可以从子段最多改变一个数（可改变为任一个整数），使子段严格地增加。

    输出找到的最长子段的长度即可。

    ★数据输入

    输入第一行为一个正整数 n

    第二行为 n 个数，第 i 个代表 ai。，0<=ai<=1000000000

    对于 30%的数据，1<=n<=666;

    对于 100%的数据，1<=n<=100086;

    ★数据输出

    输出找到的最长子段的长度即可。

    Kyungsoo(3252627372) 2022-09-08 19:51:40
    ★实验任务
    设有 n 个人偶围成一个圈，一开始都有一个编号，然后为每人偶手里都握着一个令牌，令牌上有一个数字（随机生成的），和下个倒霉人偶有关。

    第一个击的是第一个人偶，下次射击的从被打倒的人偶以后的第一个人偶开始数，往后数第 ai 个（是为其令牌上写明的数字数）。注意人偶被打到则出列。

    以上过程直到所有人都出列为止。

    ★数据输入
    第 1 行一个整数 n（1<=n<=3000），代表人偶数，

    第 2 行有 n 个空格隔开的整数代表按时间顺序被打倒的人偶的编号（1<=ai<=1000）。

    ★数据输出
    被打倒的人偶的编号
     

    1.  
    2.  
    3. #define _CRT_SECURE_NO_WARNINGS
    4. #include 
    5.  
    6. int cntAscendingLength(int[], int , int);//统计数组第start位置到size中升序的长度
    7. int cntAscendingLength(int a[], int start, int size)//统计数组第start位置到size中升序的长度
    8. {
    9. 	int cnt = 1, i = 0;
    10. 	for (i = start; i < size - 1; i++)
    11. 		if (a[i] < a[i + 1])cnt++; else return cnt;
    12. }
    13. int main()
    14. {
    15. 	int a[100086];//数组
    16. 	int i = 0;//遍历数组的游标，从0游到尾，没有回头的情况
    17. 	int n;//[1,100086]
    18. 	int ans=0;//最后结果
    19. 	int current;//i所在位置之后的长度记录
    20. 	int previous;//上一组的长度
    21.  
    22. 	scanf("%d",&n);//数组 共 n个元素
    23. 	for (i = 0; i < n; i++)//每个元素的值
    24. 		scanf("%d",a+i);
    25.  
    26. 	current = cntAscendingLength(a,0,n);//统计开始的最大增长
    27. 	previous = current;//记录当前长度
    28. 	ans = current;//第一次的长度
    29. 	i = 0;
    30. 	while (i < n ) //游标在合理范围就循环
    31. 	{		
    32. 		
    33. 		if ((i += previous) == n)break; // i加上 上次最大增长值实现向后游	 扫到尾直接退出		
    34. 		current = cntAscendingLength(a, i, n);//取i位置的最大增长长度值
    35. 		//分两种情况比较
    36. 		
    37. 		//1 当前长度与ans的比较
    38. 		//如果现在的长度比ans一样或还要长，则保存
    39. 		ans = ans <= current ? current+1 : ans;
    40.  
    41. 		//2 如果上次最大长度与本次最大长度可以拼接，再与ans比较			
    42. 		//如果i位置值改了能连接前后，则比较
    43. 		//  1 6  6  8  第2个6 要大于前面值， +1后要小于后面的值 
    44. 		if (a[i] <= a[i - 1] && a[i]+1 < a[i + 1]) 
    45. 			ans = ans < previous + current ? previous + current  : ans;	
    46. 		
    47. 		previous = current;//记录当前长度
    48. 	}
    49. 	printf("%d\n",ans);
    50. 	return 0;
    51. }
    52.  
    53.  
    54.  
    55.  
    56. //#define M 3000
    57. //int main()
    58. //{
    59. //    int i,n, a[M] = {0}, vis[M] = { 0 };
    60. //    // a[]令牌信息，vis[]已经被打倒的人偶就置1，没打倒就置0
    61. //    scanf("%d", &n); //输入人数
    62. //    for (i = 0; i < n; i++)
    63. //        scanf("%d",a+i);//每个人手里的令牌数
    64. //
    65. //
    66. //    int cur = 0, nextag; //cur当前  //nextag下一个
    67. //    for (i = 0; i < n; i++)
    68. //    {
    69. //        printf("%d ", cur + 1);//输出要倒下的当前编号
    70. //        vis[cur] = 1;//标记倒下
    71. //        nextag = a[cur];//用nextag记下倒的人手里的令牌
    72. //
    73. //        if (i < n - 1 ) // i==n-1时就只剩一个未打倒人偶了，不需要再找下一个
    74. //        {
    75. //            while (nextag)//当nextag为0 循环结束，代表找到要倒下的人的位置了
    76. //            {                
    77. //                cur = ++cur%n; //移动 范围[0到n-1]
    78. //                if (vis[cur] == 0) nextag--;//如果没位置没打倒，nextag--
    79. //            }            
    80. //        }
    81. //    }
    82. //
    83. //    return 0;
    84. //}
    85.  
    86. /*
    88. ★实验任务
    89. 设有 n 个人偶围成一个圈，一开始都有一个编号，然后为每人偶手里都握着一个令牌，令牌上有一个数字（随机生成的），和下个倒霉人偶有关。
    91. 第一个击的是第一个人偶，下次射击的从被打倒的人偶以后的第一个人偶开始数，往后数第 ai 个（是为其令牌上写明的数字数）。注意人偶被打到则出列。
    93. 以上过程直到所有人都出列为止。
    95. ★数据输入
    96. 第 1 行一个整数 n（1<=n<=3000），代表人偶数，
    97. 5
    98. 第 2 行有 n 个空格隔开的整数代表按时间顺序被打倒的人偶的编号（1<=ai<=1000）。
    99. 1 3 2 4 3
    100. ★数据输出
    101. 1 2 5 3 4
    102. 被打倒的人偶的编号
    107. */

  • 相关阅读:
    聚苯乙烯/Fe3O4纳米复合材料PS@Fe3O4|硫化锌-四氧化三铁(ZnS/Fe3O40纳米复合物（齐岳）
    [python知识巩固]特殊函数repr()
    MySQL简介
    计算机毕业设计SSM大学体育馆预约系统【附源码数据库】
    计算机网络常见面试题
    记一次 .NET某培训学校系统 内存碎片化分析
    非常全的一份Python爬虫的Xpath博文
    【verilog 设计】 reg有没有必要全部赋初值？
    2.21每日一题（隐函数求导+变上限积分求导）
    低价寄快递寄件微信小程序 实际商用版 寄快递 低价寄快递小程序（源代码+截图）前后台源码
  • 原文地址：https://blog.csdn.net/laocooon/article/details/126774180