鏈接：https://ac.nowcoder.com/acm/contest/993/E
來源：牛客網(wǎng)

對牛排序
時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld
題目描述
Farmer John正在嘗試將他的N頭奶牛（1≤N≤100），方便起見編號為1…N，在她們前往牧草地吃早餐之前排好順序。
當前，這些奶牛以p1,p2,p3,…,pN的順序排成一行，Farmer John站在奶牛p1前面。他想要重新排列這些奶牛，使得她們的順序變?yōu)?,2,3,…,N奶牛1在Farmer John旁邊。

今天奶牛們有些困倦，所以任何時刻都只有直接面向Farmer John的奶牛會注意聽Farmer John的指令。每一次他可以命令這頭奶牛沿著隊伍向后移動k步，k可以是范圍1…N?1中的任意數(shù)。她經過的k頭奶牛會向前移動，騰出空間使得她能夠插入到隊伍中這些奶牛之后的位置。

例如，假設N=4，奶牛們開始時是這樣的順序：

FJ: 4, 3, 2, 1
唯一注意FJ指令的奶牛是奶牛4。當他命令她向隊伍后移動2步之后，隊伍的順序會變成：

FJ: 3, 2, 4, 1
現(xiàn)在唯一注意FJ指令的奶牛是奶牛3，所以第二次他可以給奶牛3下命令，如此進行直到奶牛們排好了順序。

Farmer John急欲完成排序，這樣他就可以回到他的農舍里享用他自己的早餐了。請幫助他求出將奶牛們排好順序所需要的最小操作次數(shù)。

輸入描述:
輸入的第一行包含N。

第二行包含N個空格分隔的整數(shù)，p1,p2,p3,…,pN，表示奶牛們的起始順序。
輸出描述:
輸出一個整數(shù)，為Farmer John采用最佳策略可以將這N頭奶牛排好順序所需要的操作次數(shù)。
示例1
輸入
復制
4
1 2 4 3
輸出
復制
3
備注:

題意：

思路：
我們知道，一個編號為x的牛，如果右邊有一個牛的編號y使其 y<x 那么這個編號為x的牛肯定是要進行排序的， 那么我們不妨直接找最靠右的滿足這個條件的牛。即可

細節(jié)見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int a[maxn]; int n; int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin >> n;repd(i, 1, n) {cin >> a[i];}int ans = 0;for (int i = n; i >= 1; i--) {int isok = 0;for (int j = i + 1; j <= n; ++j) {if (a[i] > a[j]) {isok = 1;}}if (isok) {ans = i;break;}}cout << ans << endl;return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11285026.html

總結

以上是生活随笔為你收集整理的P5200 [USACO19JAN]Sleepy Cow Sorting 牛客假日团队赛6 D迷路的牛 （贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。