[C++知识库]acm寒假训练第二周总结

一，本周训练题型：排序

1，P1271 【深基9.例1】选举学生会

本题较为基础，套用快排模板，利用指针的移动交换完成排序

代码如下：

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
long long m;

void quick(int a[], int l, int r)
{
	if (l >= r)
		return;

	int x = a[(l + r) / 2], i = l - 1, j = r + 1;


	while (i < j)
	{
		do
			i++;

		while (a[i] < x);

		do
			j--;

		while (a[j] > x);

		if (i < j)
			swap(a[i], a[j]);
	}

	quick(a, l, j);
	quick(a, j + 1, r);
}


int main()
{

	scanf("%d%lld", &n,&m);

	for (int i = 0; i < m; i++)
		scanf("%d", &a[i]);




	quick(a, 0, m - 1);

	for (int i = 0; i < m; i++)
		printf("%d ", a[i]);

	return 0;
}

2，P1177 【模板】快速排序

存存模板代码：

#include <iostream>
using namespace std;
const int N =1e6+10;
int a[N];
int n;
void quick(int a[], int l, int r) {
	if (l >= r)
		return;

	int x = a[(l+r)/2], i = l - 1, j = r + 1;


	while (i < j) {
		do
			i++;

		while (a[i] < x);

		do
			j--;

		while (a[j] > x);

		if (i < j)
			swap(a[i], a[j]);
	}

	quick(a, l, j);
	quick(a, j + 1, r);
}


int main() {

	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);




	quick(a, 0, n - 1);

	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);

	return 0;
}

3，P1923 【深基9.例4】求第 k 小的数

本体思路为利用排序并输出目标，在于优化排序的时间复杂度

代码如下

#include<stdio.h>
int a[10000000];
int quick_sort(int *a,int low,int high)
{
    int i=low,j=high;
    int mid=(i+j)/2;
    int temp1;
    if(a[j]<a[i])
    {
        temp1=a[j];
        a[j]=a[i];
        a[i]=temp1;
    }
    if(a[j]<a[mid])
    {
        temp1=a[j];
        a[j]=a[mid];
        a[mid]=temp1;
    }
    if(a[mid]>a[i])
    {
        temp1=a[i];
        a[i]=a[mid];
        a[mid]=temp1;
    }
    int temp=a[i];
    while(i<j)
    {
        while(i<j&&a[j]>=temp)
        {
            j--;
        }
        a[i]=a[j];
        while(i<j&&a[i]<=temp)
        {
            i++;
        }
        a[j]=a[i];
    }
    a[i]=temp;
    if(i-1>low)
        quick_sort(a,low,i-1);
    if(i+1<high)
        quick_sort(a,i+1,high);
    return 0;
}
int main(void)
{
    int n,i,k;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,0,n-1);
    //for(i=0;i<n;i++)
        //printf("%d ",a[i]);
    printf("%d",a[k]);
    return 0;
}

4，P1059 [NOIP2006 普及组] 明明的随机数

本题的思路是遍历数组找寻重复的数组元素，并将其重新赋值为-1，最终根据-1的个数判断重复的次数，并从第-1之后开始输出数组达成目标

代码如下

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;

void quick(int a[], int l, int r)
{
	if (l >= r)
		return;

	int x = a[(l + r) / 2], i = l - 1, j = r + 1;


	while (i < j)
	{
		do
			i++;

		while (a[i] < x);

		do
			j--;

		while (a[j] > x);

		if (i < j)
			swap(a[i], a[j]);
	}

	quick(a, l, j);
	quick(a, j + 1, r);
}


int main()
{
	int t = 0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	quick(a, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{

			if (a[i] == a[j])
			{
				a[j] = -1;

			}
		}
		if (a[i] == -1)
			t++;


	}
	quick(a, 0, n - 1);
	printf("%d\n", n - t);
	for (int i = t; i < n; i++)
		printf("%d ", a[i]);

	return 0;
}

5，P1093 [NOIP2007 普及组] 奖学金

本题思路较为明显，主要为不遗落排序的条件，仔细阅读题干

代码如下

#include <iostream>
using namespace std;

struct person
{
	int n;//number
	int c;//chinese
	int m;//math
	int e;//english
	int sum;
};

int main()
{
	int n1;
	scanf("%d", &n1);
	struct person s[n1], temp;
	for (int i = 0; i < n1; i++)
	{
		scanf("%d%d%d", &s[i].c, &s[i].m, &s[i].e);
		s[i].sum = s[i].c + s[i].m + s[i].e;
		s[i].n = i + 1;
	}

	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = 0; j < n1 - 1 - i; j++)
		{
			if (s[j].sum < s[j + 1].sum)
			{
				temp = s[j];
				s[j] = s[j + 1];
				s[j + 1] = temp;

			}
		}
	}
	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = 0; j < n1 - 1 - i; j++)
		{
			if (s[j].sum == s[j + 1].sum)
			{
				if (s[j].c < s[j + 1].c)
				{
					temp = s[j];
					s[j] = s[j + 1];
					s[j + 1] = temp;
				}
			}
		}
	}
	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = 0; j < n1 - 1 - i; j++)
		{
			if ((s[j].sum == s[j + 1].sum) && (s[j].c == s[j + 1].c))
			{
				if (s[j].n > s[j + 1].n)
				{
					temp = s[j];
					s[j] = s[j + 1];
					s[j + 1] = temp;
				}
			}
		}
	}
	for (int i = 0; i < 5; i++)
		printf("%d %d\n", s[i].n, s[i].sum);



	return 0;
}

6，P1781 宇宙总统

本题主要为结构体的成员进行遍历，之后进行字符串的比较函数strcmp找出最大成员票数的下标值

最终输出该人的顺序和最大票数

代码如下

#include <iostream>
#include <string.h>
using namespace std;

struct person
{
	int n;//number
	char a[110];//ticket
	int t;//length
};
char ma[110] = "";

int main()
{
	int n1, max1 = 0, k;
	scanf("%d", &n1);
	struct person s[n1];
	for (int i = 0; i < n1; i++)
	{
		scanf("%s", s[i].a);
		s[i].n = i + 1;
		s[i].t = strlen(s[i].a);
	}
	for (int i = 0; i < n1; i++)
	{
		if (strlen(ma) < s[i].t || strlen(ma) == s[i].t && strcmp(ma, s[i].a ) < 0)
		{
			strcpy(ma, s[i].a);
			k = i;
		}


	}
	printf("%d\n%s\n", k + 1, ma);



}

7，P2676 [USACO07DEC]Bookshelf B

该题思路主要为从大到小排序，之后累加判断是否超出条件找到临界值输出，不过在排序的优化上花费许多时间，最终在观看题解的帮助下利用冒泡排序完成

代码如下

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, m;


int main()
{
	int sum = 0, t = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] < a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
//	for (int i = 0; i < n; i++)
	//	printf("%d ", a[i]);
//	printf("\n\n");

	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		t += 1;
		if (sum >= m)
		{
			printf("%d", t);
			return 0;
		}
	}
}

8，P1116 车厢重组

本题即为计算排序的次数输出即可

代码如下

#include <iostream>
using namespace std;
int a[100000];
int n;

int main()
{
	int k = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (a[i] > a[j])
			{
				k++;
			}
		}
	}
	printf("%d", k);


	return 0;
}

9，P1152 欢乐的跳

本题首先利用原来的数组元素进行相减。在取绝对值保存至新的数组中，在进行排序，最后判断新数组中元素是否一一对应1——n-1的元素

代码如下

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	int n, i, j = 0, t = 0, temp;
	scanf("%d", &n);
	int a[n], b[n];
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; i++)
	{
		temp = a[i] - a[i + 1];
		b[j] = fabs(temp);
		j++;
	}
	for (int i = 0; i < j - 2; i++)
	{
		for (int k = i + 1; k < j - 1; k++)
		{
			if (b[i] > b[k])
			{
				int temp1 = b[i];
				b[i] = b[k];
				b[k] = temp1;
			}

		}
	}
	//for (int i = 0; i < j - 1; i++)
	//	printf("%d", b[i]);
	for (int i = 1; i <= n - 1; i++)
	{
		for (int k = 0; k < j - 1; k++)
		{
			if (b[k] == i)
				t++;
		}
	}
	if (t == n - 1)
		printf("Jolly");
	else
		printf("Not jolly");
	return 0;
}

10，P1068 [NOIP2009 普及组] 分数线划定

该题在于利用给出的条件判断界定线，并在按照要求排序后输出满足条件的人数

代码如下

#include <iostream>
#include <math.h>
using namespace std;
struct person
{
	int n;//number
	int g;//score
};
int main()
{
	int n1, m, k, t1, k1;
	float t;
	scanf("%d%d", &n1, &m);
	struct person s[n1], temp;
	for (int i = 0; i < n1; i++)
		scanf("%d %d", &s[i].n, &s[i].g);
	for (int i = 0; i < n1 - 1; i++)
		for (int j = i + 1; j < n1; j++)
		{
			if (s[i].g < s[j].g)
			{
				temp = s[i];
				s[i] = s[j];
				s[j] = temp;
			}
		}
	t = m * 1.5;
	t1 = floor(t) - 1;
	k = s[t1].g;
	printf("%d", k);
	for (int i = 0; i < n1; i++)
	{
		if (s[i].g < k)
		{
			k1 = i;
			printf(" %d\n", k1);
			break;
		}
	}
	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = i + 1; j < n1; j++)
		{
			if (s[i].g == s[j].g)
			{
				if (s[i].n > s[j].n)
				{
					temp = s[i];
					s[i] = s[j];
					s[j] = temp;
				}
			}
		}
	}
	for (int i = 0; i <k1; i++)
		printf("%d %d\n", s[i].n, s[i].g);
	return 0;
}

11，P5143 攀爬者

?该题在于用结构体保存x,y,z三个坐标数据，并以z的大小作为判断条件从小到大排序，最后按照题中所给条件输出结果，不过该题我的代码仍存在一些问题

代码如下

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

struct high
{
	int x;
	int y;
	int z;
};

int main()
{
	long long n;
	scanf("%lld", &n);
	double sum = 0, sum1;
	struct high s[n], temp;
	for (int i = 0; i < n; i++)
		scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].z);
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (s[j].z > s[j + 1].z)
			{
				temp = s[j];
				s[j] = s[j + 1];
				s[j + 1] = temp;
			}
		}
	}
	//printf("%d %d %d\n", s[i].x, s[i].y, s[i].z);

	for (int i = 0; i < n - 1; i++)
	{
		sum1 = (s[i].x - s[i + 1].x) * (s[i].x - s[i + 1].x) + (s[i].y - s[i + 1].y) * (s[i].y - s[i + 1].y) +
			   (s[i].z - s[i + 1].z) * (s[i].z - s[i + 1].z);
		sum1 = fabs(sum1);
		sum1 = sqrt(sum1);
		sum += sum1;
	}
	printf("%.3lf", sum);





	return 0;
}

12，P1104 生日

本题为简单的结构体多次排序，年月相同情况再次进行排序即可

代码如下

#include <iostream>
using namespace std;

struct person
{
	int n;//number
	char name[10];
	int y;//year
	int m;//month
	int d;//date
};

int main()
{
	int n1;
	scanf("%d", &n1);
	struct person s[n1], temp;
	for (int i = 0; i < n1; i++)
	{
		scanf("%s %d %d %d", s[i].name, &s[i].y, &s[i].m, &s[i].d);
		s[i].n = i + 1;
	}
	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = i + 1; j < n1; j++)
		{
			if (s[i].y > s[j].y)
			{
				temp = s[i];
				s[i] = s[j];
				s[j] = temp;
			}
		}
	}
	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = i + 1; j < n1; j++)
		{
			if (s[i].y == s[j].y)
			{
				if (s[i].m > s[j].m)
				{
					temp = s[i];
					s[i] = s[j];
					s[j] = temp;
				}
			}
		}
	}
	for (int i = 0; i < n1 - 1; i++)
	{
		for (int j = i + 1; j < n1; j++)
		{
			if (s[i].y == s[j].y && s[i].m == s[j].m)
			{
				if (s[i].d > s[j].d)
				{
					temp = s[i];
					s[i] = s[j];
					s[j] = temp;
				}
			}
		}
	}

	for (int i = 0; i < n1; i++)
		printf("%s\n",s[i].name);


}

13，P1012 [NOIP1998 提高组] 拼数

本题对于现在的我仍是一道难题，在借助题解大佬的帮助下使用c++中的string的变量进行直接比较完成此题

代码如下

#include <bits/stdc++.h>
using namespace std;
string a[30];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{

			if (a[j] + a[i] > a[i] + a[j])
				swap(a[j], a[i]);
		}
	}
	for (int i = 0; i < n; i++)
		cout << a[i];

	return 0;

}

二，本周总结

1，本周投入时间较少，由于一些额外不得以避免的事情所耽误，所以写的比较匆忙，不过会在之后慢慢补上。

2，其次，本周的题型也是围绕快速排序、选择排序、冒泡排序进行解题，其中在在快速排序初步了解下也是学习甚多，也拓宽了更多的知识储备。