每日一题:不休独舞（贪心算法）（芙宁娜，我的芙芙）

本文主要是介绍每日一题:不休独舞（贪心算法）（芙宁娜，我的芙芙），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A 不休独舞

时间限制: 1000MS 空间限制: 128MB

题目描述

beiheng 学长正在玩原神。

苦苦等待芙宁娜好几个月，终于可以抽了，300抽大战3+1，他在看芙宁娜的技能时（芙宁娜和她的动物朋友们），灵感突发，想到一个这样的“贪心”的题目。

现在有一个长度为 n的序列，这个序列的每个位置都有一位 孤心沙龙上的客人 （以下简称客人），其中第 i位客人的气氛值为 ai，芙宁娜拥有一个技能，可以将任意一位客人的气氛值除以 2 并下取整，具体而言，若一位客人的气氛值为 x，则使用技能以后它的气氛值会变为 ⌊x/2⌋，芙宁娜可以使用任意次技能。

我们称一个序列是严格递增的，当且仅当对于任意 i<j，都有 ai<aj。

芙宁娜希望这个序列上的客人气氛值满足严格递增，以完成一场盛大的演出，同时他也希望她需要使用的技能次数最少，你需要输出这个最小值，若无法保证序列严格递增请输出 sabishii。

输入描述

输入的第一行包含一个整数 T ( 1≤T≤10^4)，表示数据组数。

对于每组数据：

第一行都包含一个整数 n( 1≤n≤30 )表示序列的客人的个数。

第二行包含 n个整数 a1,a2,…,an（ 0≤ai≤2⋅10^9）。

输出描述

共 T行，每行一个整数 d 表示答案 —— 要使序列严格递增，需要对序列执行的最小运算次数。如果无法得到严格递增序列，则输出 sabishii。

样例

输入复制

7
3
3 6 5
4
5 3 2 1
5
1 2 3 4 5
1
1000000000
4
2 8 7 5
5
8 26 5 21 10
2
5 14

输出复制

2
sabishii
0
0
4
11
0

提示

在第二个测试案例中，不可能得到严格递增序列。

在第三个测试案例中，序列已经严格递增。

问题分析：

对芙宁娜使用贪心吧，咱们要想使客人气氛值严格递增，可以反向思考，for从最后i=n-1开始i--，对是否能严格递增进行判断，和能不能实现进行判断。

代码实现：

#include<bits/stdc++.h>
using namespace std;
#include<cmath>
const int N=90;
#define long long int
int gu[N];//guest客人
int main(){//芙芙，我的芙芙int T;cin>>T;while (T--){int n;cin>>n;for(int i=0;i<n;i++)cin>>gu[i];int skill=0,flag=0;for(int i=n-1;i>0;i--){if(gu[i]<=gu[i-1]){while (gu[i]<=gu[i-1]){gu[i-1]=floor(gu[i-1]/2);//向下取整skill++;if(gu[i-1]==0&&i!=1){flag=1;             //早判断结束循环，减少时间复杂度cout<<"sabishii"<<endl;  //但是要注意的点是不能return 0，这样下一组数据不能输入了break;}}}if(flag)break;}if(flag==0)cout<<skill<<endl;}
}

//芙宁娜最可爱了，最伟大了，我的芙芙什么时候满命啊。

或者还有一种比较“牛”的写法那就是运用goto，减少flag的多次运用和判断，但是一定要记得T--，goto在循环里T不能进行--的。

#include<bits/stdc++.h>
using namespace std;
#include<cmath>
const int N=90;
#define long long int
int gu[N];
int main(){//芙芙，我的芙芙int T;cin>>T;while (T--){rebe:int n;cin>>n;for(int i=0;i<n;i++)cin>>gu[i];int skill=0;for(int i=n-1;i>0;i--){if(gu[i]<=gu[i-1]){while (gu[i]<=gu[i-1]){gu[i-1]=floor(gu[i-1]/2);skill++;if(gu[i-1]==0&&i!=1){cout<<"sabishii"<<endl;T--;goto rebe;//goto终于找到地方用了，bushi}}}}cout<<skill<<endl;}
}