欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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;
} 

 

相关标签: 算法基础