【ACM入门】入门问题
程序员文章站
2022-05-22 10:16:14
...
最大利益问题
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;
int main() {
int R[MAX], n;
cin >> n;
for(int i = 0; i < n; i++) cin >> R[i];
int maxv = -200000000;
int minv = R[0];
// 关键找到前面的最小的,和后面的最大的
for(int i = 1; i < n; i++) {
maxv = max(maxv, R[i] - minv); /***/
minv = min(minv, R[i]); /****/
}
cout << maxv <<endl;
return 0;
}
初等排序
插入排序
扑克牌排列手牌,把无序的放到有序的中。
#include <stdio.h>
void trace(int A[], int N) {
int i;
for ( i = 0; i < N; i++) {
if (i > 0) printf(" ");
printf("%d", A[i]);
}
printf("\n");
}
void insertionSort(int A[], int N) {
int j, i, v;
for(i = 1; i < N; i++) {
v = A[i]; //待移动的数暂时保存A[i]
j = i - 1; //从后往前找第一个小于A[i]的数的下标
while(j >= 0 && A[j] > v) {
A[j+1] = A[j]; //如果存在 ,整体往后移
j--;
}
A[j+1] = v;
trace(A, N);
}
}
int main() {
int N, i, j;
int A[100];
scanf("%d", &N);
for( i = 0; i < N; i++) scanf("%d", &A[i]);
trace(A, N);
insertionSort(A, N);
return 0;
}
冒泡排序
void bubbleSort(int A[], int N) {
int sw = 0;//交换次数
bool flag = 1;
// 如果一轮没有发生交换,循环结束
for (int i = 0; flag; i++) {
flag = 0; //表示次轮还没开始交换
for (int j = N - 1; j >= i + 1; j--) {
if( A[j] < A[j - 1]) {
// 如果后面的比前面小交换
swap(A[j], A[j - 1]); // iostream
flag = 1; // 表示交换了
sw++
}
}
}
}
选择排序
int selectionSort(int A[], int N) {
int i, j, t, sw = 0, minj;
for( i = 0; i < N - 1; i++) {
minj = i; //记录自小值的下标
for(j = i; j < N; i++) {//获取未排序数中的最小值
minj = i;
for (j = i; j < N; j++) {
if( A[j] < A[minj]) minj = j;
}
}
t = A[i]; A[i] = A[minj]; A[minj] = t;
if( i != minj ) sw++;
}
return sw;
}