小白月赛——命运之弹
核心思想：贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。
-
枚举可能的幸运值：代码中通过一个循环从给定的幸运值
x开始，一直枚举到99（假设最大幸运值为 100），遍历每个可能的幸运值，每一种可能的幸运值是由扭转乾坤得到的。 -
计算每个幸运值下的最小使用次数：对于每个幸运值，代码计算出在该幸运值下，小 K 需要使用多少次「转瞬即逝」魔法来避免被击中。这是通过比较当前幸运值与每个子弹的危险值来实现的。如果当前幸运值小于子弹的危险值，则需要使用一次「转瞬即逝」。
-
选择最小使用次数：在所有可能的幸运值中，选择需要使用「转瞬即逝」次数最少的那个幸运值作为最终结果。
注：INT_MAX 是 C++ 标准库中定义的一个常量，它表示 int 类型能够表示的最大值。
为什么会想到用贪心
1. 理解问题
首先，理解问题的需求和限制条件。在这个问题中，小 K 需要避免被子弹击中，可以通过使用两种魔法：「转瞬即逝」和「扭转乾坤」。目标是最小化使用「转瞬即逝」的次数。
2. 分析问题的局部最优解
贪心算法的核心是找到问题的局部最优解，并希望这些局部最优解能组合成全局最优解。在这个问题中，局部最优解可以是：
-
选择一个幸运值，使得需要使用「转瞬即逝」的次数最少。
-
在需要时，使用「扭转乾坤」来永久改变幸运值，以减少未来的「转瞬即逝」使用次数。
3. 识别贪心选择的性质
在这个问题中，贪心选择的性质可能包括：
-
选择当前幸运值时，考虑哪些子弹的危险值可以被「扭转乾坤」永久改变，从而减少未来的「转瞬即逝」使用。
-
在每个幸运值下，计算需要使用「转瞬即逝」的次数，并选择次数最少的幸运值。
4. 设计算法
基于上述分析，可以设计如下算法：
-
初始化一个变量
ans为INT_MAX，用于存储最小使用次数。 -
对于每个查询，枚举从给定幸运值到最大可能幸运值的所有可能幸运值。
-
对于每个幸运值，计算需要使用「转瞬即逝」的次数，并更新
ans。 -
在所有可能的幸运值中，选择使得
ans最小的幸运值。
5. 验证贪心策略的正确性
在设计算法后，需要验证贪心策略的正确性。这通常涉及到证明局部最优解能导致全局最优解，或者通过反证法证明其他策略不会得到更好的结果。
6. 实现代码
最后，根据设计的算法实现代码，并进行测试以确保其正确性和效率。
在这个问题中，贪心算法的直觉来自于对问题的直观理解：在每个步骤中选择当前最优的幸运值，同时考虑「扭转乾坤」的机会，以最小化「转瞬即逝」的使用次数。这种方法简单且直观，通常在类似问题中能有效地找到解决方案。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N];
int main(){ios::sync_with_stdio(false);cin.tie(0);//关闭 C++ 的 I/O 同步，加速输入输出cout.tie(0);//解除 cin 和 cout 的绑定，进一步提高 I/O 效率int n,ans=INT_MAX;//ans 初始化为最大整数值cin>>n;for(int i=0;i<n;i++) cin>>a[i];int q;cin>>q;while(q--){int p,x; //因为幸运值i不能随便改动，所以用p暂时存储cin>>x;for(int i=x;i<=100;i++){ //遍历每个可能的幸运值p=x;int cnt=0;for(int j=0;j<n;j++){if(a[j]==i) p=a[j]; //每个可能的幸运值至多会有一个危险值与之对应满足扭转乾坤至多可以使用1次else if(p<a[j]) cnt++;}ans=min(ans,cnt); //取每个可能的幸运值中的min}cout<<ans<<endl;}return 0;
}