首页 > 代码库 > 从零单排PAT1019,1020,1021,1022

从零单排PAT1019,1020,1021,1022

2024-07-08 00:42:59   229人阅读


1019数字黑洞  题目要求：

给定任一个各位数字不完全相同的4位正整数，如果我们先把4个数字按非递增排序，再按非递减排序，然后用第1个数字减第2个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的6174，这个神奇的数字也叫Kaprekar常数。

例如，我们从6767开始，将得到

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...

现给定任意4位正整数，请编写程序演示到达黑洞的过程。

输入格式：

输入给出一个(0, 10000)区间内的正整数N。

输出格式：

如果N的4位数字全相等，则在一行内输出“N - N = 0000”；否则将计算的每一步在一行内输出，直到6174作为差出现，输出格式见样例。注意每个数字按4位数格式输出。

输入样例1：
6767
输出样例1：
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
输入样例2：
2222
输出样例2：
2222 - 2222 = 0000
解题思路：就是一个简单的排序，我是以字符串的形式存储，然后将数字从大到小，从小到大排列，并计算得出对应的数值，最后相减就可以计算，由于题目已经是4位数，所以可以直接分配数据空间，但是需要注意的一个case是如果计算的结果不是四位数那该怎么办？排序还是一样的，注意直接输出字符串，不要输出数字（可能会出现三位数）；如果所有数字相同，输出0000。


源代码：

#include <iostream>
#include <algorithm>

using namespace std;
int compareS(const void *a,const void *b)
{
	return *(int*)a > *(int*)b;  //升序排列
}
int compareJ(const void *a,const void *b)
{
	return *(int*)a < *(int*)b;  //降序排列
}
int getNumber(int a)
{
	int d = a;
	int b = 0;
	int c[4] = {0,0,0,0}; //存储第一个数字
	int e[4] = {0,0,0,0}; //存储第二个数字
	int result = 0;
	for(int i=0;i<4;i++)
	{
		c[i] = d % 10;
		e[i] = d % 10;
		d = d/10;
	}
	qsort(&c[0],4,sizeof(int),compareJ);
	qsort(&e[0],4,sizeof(int),compareS);
	a = 0;
	for(int i=0;i<4;i++)
	{
		a = a*10 + c[i];  //得到实际数字
		b = b*10 + e[i];
	}
	result = a - b;
	if(result != 0 && result >= 1000)
	{
		cout << a << " " << "-" << " " << c[3] << c[2] << c[1] << c[0] << " " 
		<< "=" << " " << result << endl;
	}
	else if(result == 0)
	{
		cout << a << " " << "-" << " " << c[3] << c[2] << c[1] << c[0] << " " 
		<< "=" << " " << "0000" << endl;
	}
	else //只会出现3位数，不可能出现小于3位数
	{
		cout << a << " " << "-" << " " << c[3] << c[2] << c[1] << c[0] << " " 
		<< "=" << " " << '0' << result << endl;
	}
	return result;
}

int main()
{
	int num;
	cin >> num;
	do	//必须要执行第一个计算
	{
		num = getNumber(num);
	}while( num != 6174 && num != 0);
	system("pause");
	return 0;
}

1020月饼  题目要求：

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：

每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。

输入样例：
3 20
18 15 10
75 72 45
输出样例：
94.50

解题思路：这其实就是一个简单的贪婪算法，先根据单价最高的进行计算，如果单价最高的总量不能满足，则用单价第二高的，以此类推，直到达到市场最大需求量。因为一直有几个case过不去，后来看看别人的代码，是因为自己的对于总量和单价都用int型表示，在这里不够准确，索性都用float类型，也省去了强类型转换的问题。还有一个是，cout的标准输出，输出小数点后两位，用cout.setf(ios::fixed); 


源代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> 
using namespace std;
void swap (int *a,int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void swap(float *a,float *b) //重载
{
	float temp = *a;
	*a = *b;
	*b = temp;
}
int main()
{
	int N,max;//不同的个数，最大吨数
	cin >> N >> max;
	vector<float> kucun;//库存数量
	vector<float> zongjia;//各个总价
	vector<float> per;
	for(int i=0;i<N;i++)
	{
		float temp ;
		cin >> temp;
		kucun.push_back(temp);
	}
	for(int i=0;i<N;i++)
	{
		float temp ;
		cin >> temp;
		zongjia.push_back(temp);
		per.push_back((float)temp/kucun[i]);
	}
	for(int i=0;i<N-1;i++) //冒泡排序
	{
		for(int j=0;j<N-1;j++)
		{
			if(per[j]<per[j+1])  //数组降序排列
			{
				swap(per[j],per[j+1]);
				swap(kucun[j],kucun[j+1]);
				swap(zongjia[j],zongjia[j+1]);
			}
		}
	}
	int residue = max;//剩余吨数
	float income = 0; //实际收益
	int temp;
	int count;
	for(count=0;count<N;count++)
	{
		temp = residue - kucun[count];
		if(temp < 0)
		{
			income += residue * per[count];  //得到总收益
			break;
		}
		else
		{
			residue = temp;
			//income += kucun[i] * per[i];  //得到总收益
			income += zongjia[count];
		}
	}
	cout.setf(ios::fixed); 
	cout << setprecision(2) << income ;
	system("pause");
	return 0;
}





1021个位数统计  题目要求：

给定一个k位整数N = dk-1*10k-1 + ... + d1*101 + d0 (0<=di<=9, i=0,...,k-1, dk-1>0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定N = 100311，则有2个0，3个1，和1个3。

输入格式：

每个输入包含1个测试用例，即一个不超过1000位的正整数N。

输出格式：

对N中每一种不同的个位数字，以D:M的格式在一行中输出该位数字D及其在N中出现的次数M。要求按D的升序输出。

输入样例：
100311
输出样例：
0:2
1:3
3:1

解题思路：这是一道不能再简单的题目，所以没什么可说的


源代码：

#include <iostream>
#include <string>
using namespace std;
int main()
{
	string num;
	int a[10] = {0,0,0,0,0,0,0,0,0,0};
	//int a[10];
	//memset(a,0,sizeof(a));
	cin >> num;
	int lenth = num.size();
	for(int i=0;i<lenth;i++)
	{
		switch(num[i])
		{
		case '0':a[0]++;break;
		case '1':a[1]++;break;
		case '2':a[2]++;break;
		case '3':a[3]++;break;
		case '4':a[4]++;break;
		case '5':a[5]++;break;
		case '6':a[6]++;break;
		case '7':a[7]++;break;
		case '8':a[8]++;break;
		case '9':a[9]++;break;
		}
	}
	for(int i=0;i<10;i++)
	{
		if(a[i] != 0)
		{
			cout << i << ":" << a[i] <<endl;
		}
	}
	system("pause");
	return 0;
}



1022 D进制 A+B 题目要求：

输入两个非负10进制整数A和B(<=230-1)，输出A+B的D (1 < D <= 10)进制数。

输入格式：

输入在一行中依次给出3个整数A、B和D。

输出格式：

输出A+B的D进制数。

输入样例：
123 456 8
输出样例：
1103

解题思路：这是计算机相关专业的基础知识，需要知道只是怎么计算D进制数，因为数都小于2的30次-1，所以可以用int型直接存储，相加得到的数据整除D，最后逆序输出即可得到D进制数（原本是先得到10进制数，但随后就发现，只要把10换成D，就可以得到D进制数），但需要注意的case是两个非负的整数相加可能为0，所以考虑0时，输出0。


源代码：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	unsigned int A,B,D;
	vector <int> a;  //存储10进制数
	vector <int> b;	//存储N进制数
	cin >> A >> B >> D;
	unsigned int temp = A + B;
	if(temp == 0) //如果=0时，因为都是非0，这个条件要考虑
	{
		cout << '0' << endl;
		system("pause");
		return 0;
	}
	else
	{
		while(temp!=0)
		{
			a.push_back(temp % D);
			temp /= D;
		}
		int lenth = a.size();
		for(int i=0;i<lenth;i++)
		{
			cout << a[lenth - i - 1]; 
		}
		cout << endl;
		system("pause");
		return 0;
	}
}



联系
我们