如果有 $a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n$，则称长度为 $n$ 的数组 $a$ 已排序。
Ntarsis 有一个长度为 $n$的数组 $a$。
他可以对数组进行一种操作（0 次或多次）：
- 选择一个索引 $i$（$1 \leq i \leq n-1$）。
- 将$1$加到$a_1, a_2, \ldots, a_i$。
- 用$a_{i+1}, a_{i+2}, \ldots, a_n$减去$1$。操作后，$a$的值可能是负数。
确定使$a$**不排序所需的最少运算。**不排序**。
即使用最少的操作使数组无序。
#include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<string.h> #include<set> #include<string> #include<map> #include<iostream> #include<queue> #include<unordered_set> #include<stdlib.h> #include<sstream> #include<iomanip> typedef long long ll; using namespace std; const int Mod=1e9+7; const int N=1e5+7; int T; int n,q,m; int main() { cin>>T; while(T--) { int a[510],b[510]; cin>>n; cin>>a[0]; int flag=0,Min=1000000000; int l,r; for(int i=1;i<n;i++) { cin>>a[i]; b[i]=a[i]-a[i-1]; if(a[i]-a[i-1]>=0) { if(b[i]<=Min) { Min=b[i]; l=a[i-1]; r=a[i]; } flag++; } } if(flag==n-1) { int op=0; if((l+r)%2==0) { op=(r-l)/2+1; } else { op=(r-l)/2+1; } cout<<op<<endl; } else { cout<<0<<endl; } } system("pause"); return 0; }
即求第k位是n的类斐波那契数列的个数。
思路：由于已知第k位，通过遍历k-1位反向还原到第一位，并判断第一位是否大于零或中途数组为非递减。
#include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<string.h> #include<set> #include<string> #include<map> #include<iostream> #include<queue> #include<unordered_set> #include<stdlib.h> #include<sstream> #include<iomanip> typedef long long ll; using namespace std; const int Mod=1e9+7; const int N=1e5+7; int T; int n,q,m; int main() { cin >> T; while(T--){ int n,k; cin >> n >> k; int a3=n,a2,a1; int cnt = 0; for(int i = n;i >= (n+1)/2;i--){ a3=n; a2=i; int j; for(j = k-2;j >= 1;--j){ a1 = a3 - a2; int ta2=a2; a3=a2; a2=a1; if((a1 <= 0&&j!=1)||a1>ta2) { break; } } if(a1 >= 0 && j < 1) { cnt++; } } cout << cnt << endl; } system("pause"); return 0; }