Problem description :

You must have heard the story of Tian Ji's horse racing ? If 3 A horse becomes n Horse (n<=100), The king of Qi still let his horse compete in the first round in the order of good to bad , Tian Ji can choose his horse race in any order . Win a game , Tian Ji can get 200 Two silver ; Lose a game , Tian Ji will lose 200 Two silver . The running speed of all horses of king and Tian Ji has been known , And all horses run at different speeds , Their horses have been arranged from fast to slow . Please design an algorithm , Help Tian Ji win the most Silver .

requirement :
(1) Write pseudo code .
(2) utilize C or C++ code , The above algorithm is realized by programming .
input : The first line is an integer n, It means that both parties have their own n Horses ; Second line n Integers represent Tian Ji's n The speed of a horse ; Third line n Integers represent the of king Qi respectively n Horse speed .
output : If you plan carefully through smart , If you can win the game ( The number of wins is more than half of the total number of games ), Then output “YES”.
Otherwise output “NO”. And output an integer , How much gold can Tian Ji win at most .

Experimental principle :

If Tian Ji's fastest horse is faster than king Qi's fastest horse , Then compare it
If Tian Ji's fastest horse is slower than king Qi's fastest horse , Then compare the slowest horse in the field with the fastest one
// This is the first step of greed
If the speed of Tian Ji's fastest horse is equal to that of king Qi Wei's fastest horse
If Tian Ji's slowest is faster than Qi Weiwang's slowest , Then compare it
// This is the second step of greed
If Tian Ji's slowest is slower than Qi Weiwang's slowest , Tian Jiman VS Qi Wangkuai
Tian Ji's slowest is equal to that of King Wei of Qi , Tian Jiman VS Qi Wangkuai

Experimental procedure :

#include <iostream> #include <cstdlib> using namespace std; // Quick row void Quick(
int a[], int begin, int end) { if (begin >= end) return; int t = a[begin]; int i
= begin; int j = end; while (i < j) { while (i<j && a[j] < t) j--; a[i] = a[j];
while (i < j && a[i] >= t) i++; a[j] = a[i]; } a[i] = t; Quick(a, begin, i - 1);
Quick(a, i + 1, end); } // Tianji horse racing algorithm int tianRac(int Tian[], int King[], int n) {
int money = 0; // Tian Ji won the money int tianh = 0, tiane = n-1, kingh = 0, kinge = n-1; //
Mark the fastest and slowest horses of Tian Ji horse team and Qi Wang horse team respectively // share n Games , Every time , Just change to another horse ( Grandpa Tian is in position , Start the horse race show ) for (int i = 0; i <
n; i++) { // When Tian Ji's fast horse is faster than king Qi's fast horse , Then compete with him ( Gambling monster , Must win ) if (Tian[tianh] > King[kingh]) { money
+= 200; tianh++; // next kingh++; // next } //
When Tian Ji's fast horse is slower than king Qi's fast horse , Compare the slowest horse with his fastest ( Ambush him , This horse doesn't have to be robbed , He's dead , Backhand a super double , Make a fortune in silence ) else if (Tian[tianh] <
King[kingh]) { money -= 200; tiane--; kingh++; } //
When Tian Ji's fast horse is as fast as king Qi's fast horse ( He's just as fast ? But don't be afraid , His horse can't beat me ) else { // When Tian Ji's slow horse is faster than king Qi's slow horse ( This horse is awesome ) if (Tian[
tiane] > King[kinge]) { money += 200; tiane--; kinge--; } //
Tian Ji's slow horse is as fast and slow as king Qi's slow horse , Compare him with a slow horse ( If this slow horse is replaced by a fast horse, my horse will be killed , Unfortunately, I can't change it ) else { money -= 200; tiane
--; kingh++; } } } // Return the money Tian Ji won return money; } int main() { int n; // Number of horses on both sides of the race
cout<< " Equidistant horse geometry " << endl; cin >> n; int* Tian = new int[n]; int* King = new int[n]
; cout << " general Disease of horse " << endl; for (int i = 0; i < n; i++) { cin >> *(Tian + i); }
cout<< " king Disease of horse " << endl; for (int i = 0; i < n; i++){ cin >> *(King + i); } //
sort , Descending order Quick(Tian, 0, n-1); Quick(King, 0, n - 1); // call “ Even if the Buddha comes , Grandpa Tian is hard to lose ” function int
result= tianRac(Tian, King, n); if (result > 0) { cout << " general win " << endl; cout
<< " win " << result << " gold " << endl; } else if (result == 0) { cout << " and " << endl;
} else { cout << " king win " << endl; cout << " win " << -result << " gold " << endl; } return
0; }
Experimental test :

Complexity analysis :
take tj Horse speed and king The speed of horses is sorted from small to large , Then compare the horses in three cases , The time complexity is o(N)

Technology
©2019-2020 Toolsou All rights reserved,
evo Tool usage problems ——Degenerate covariance rank, Umeyama alignment is not possible Experiment 4 Automated test tools - software test mysql Export data sql sentence _mysql according to sql Query statement export data Create a thread ——— Javaweb (3) Data structure experiment ( three )—— Stacks and queues TS stay vue2 Writing in the project web Front end signature plug-in _signature_pad Plug in implements electronic signature function docker Where is the image stored Qt Getting Started tutorial 【 Basic controls 】QCalendarWidget calendar control springboot How to get reality in ip address