题解：摧毁树桩的最少炸药数量

题目分析

本题要求找到最少的引爆点，使得每个树桩要么被直接引爆，要么被连锁摧毁。关键在于利用“严格递减连锁反应”的特性，确定每个引爆点能覆盖的最大区间。

解题思路

1. 观察规律：

   • 当引爆一个树桩时，其左右两侧会形成严格递减的序列。因此，对于连续递增的序列，必须在其峰值处引爆（否则无法覆盖后续更高的树桩）。
   • 例如，序列1 2 5 4 3中，引爆5（峰值）可覆盖左侧2,1和右侧4,3。

2. 算法逻辑：

   • 遍历树桩序列，寻找“极大点”（即当前树桩比下一个树桩高或相等的位置）。
   • 当遇到递增序列时（a[j] > a[j-1]），继续向后遍历；当遇到递减或相等时（a[j] <= a[j-1]），当前位置j为一个极大点，需引爆。
   • 引爆后，跳过该区间内已被覆盖的树桩，继续处理后续部分。

3. 复杂度：

   • 时间复杂度：最坏情况下为 ( O(N^2) )，但在实际数据中，由于每次引爆后跳过一段区间，效率较高，可通过题目给定的约束（( N \leq 50,000 )）。

代码解释

#include <iostream>
using namespace std;
int main()
{
	int a[50005];
	int n;
	cin>>n;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
	} 
	for(int i = 0; i < n; i++)
	{
		if(i + 1 == n)
		{
			cout<<i+1<<endl;
			break;
		}
		for(int j = i + 1; j < n; j++)
		{
			if(a[j] > a[j-1])
			{
				if(j + 1 == n)
				{
					cout<<j+1<<endl;
					i = n;
					break;	
				}
				continue;
			}
			cout<<j<<endl;
			for(int k = j; k < n; k++)
			{
				if(a[k] < a[k-1])
				{
					if(k + 1 == n)
					{
						i = n;
						j = n;
					 	break;
					}					
					continue;
				}
				i = k - 1;
				j = n;
				break;
			}
		}
	}
	return 0;
}

关键步骤

1. 输入处理：读取树桩高度数组a。
2. 遍历寻找极大点：
   • 外层循环i表示当前处理的起始位置。
   • 内层循环j从i+1开始，寻找第一个满足a[j] <= a[j-1]的位置j，该位置即为当前区间的极大点，需引爆。
   • 若遇到连续递增（如a[j] > a[j-1]），则继续向后遍历，直到序列结束或找到递减点。
3. 输出索引：引爆点的索引为j（数组下标从0开始，输出时对应题目要求的1-based索引）。

样例验证

对于输入样例：

9  
1 2 5 4 3 3 6 6 2  

• 遍历过程：
  • i=0，j=1（2>1，递增）→ j=2（5>2，递增）→ j=3（4<5，触发条件），输出j=3（索引3对应题目中的3号树桩）。
  • i更新为j-1=2，继续处理剩余部分（下标3~8）。
  • i=2，j=3（3号树桩已处理，跳过）→ j=5（3=3，触发条件），输出j=5？不，实际剩余序列为3,6,6,2，正确逻辑应为：
    • 在剩余序列中，j=5（值3）的下一个位置j=6（6>3，递增）→ j=7（6=6，触发条件），输出j=7（对应题目中的7号树桩）。
    • 继续处理j=7之后，j=8（2<6，触发条件），输出j=8（对应题目中的8号树桩）。
• 最终输出3,7,8，与样例一致。

注意事项

• 代码中的索引处理：数组下标从0开始，输出时直接使用j（对应题目中的1-based索引）。
• 内层循环通过i = j - 1跳过已处理区间，避免重复计算，提高效率。

此代码通过贪心策略每次选择极大点引爆，确保用最少的炸药覆盖所有树桩，虽时间复杂度非最优，但能正确解决问题。