每日编程中遇到任何疑问、意见、建议请公众号留言或直接撩Q474356284(备注每日编程)
鲁大师和他的朋友们经常去一家奇怪的餐厅,为什么说奇怪呢,一是餐厅提供的菜品比较奇怪,二是餐厅的付费规则比较奇怪,每个人有不同的折扣率和折扣上限(单人从总价里折算的最高金额),超过折扣上限的原价付费。这次鲁大师和蔚然晨风以及朋友们一共N个人去这家餐厅吃饭,他们点的菜品总价是T,现在告诉你每个人的折扣率z和折扣上限H请告诉他们最少需要支付多少钱。
输入格式:
输入数据有多组,每组占N+1行,第一行是N和T,接下来N行,每行两个数字z和H(输入数据保证最后结果为int型,0<N<100)
输出格式:
对于每组输入数据,输出一行,对应一个要求的答案。
输入样例:
2 100
0.7 70
0.6 50
3 500
0.6 100
0.8 200
0.7 100
1 100
0.6 100
输出样例:
65
390
60
解决方法:
(1)算法的基本思想:
算法思想:设计一个二维数组a,第一列a[0]存储折扣率,第二列a[1]存储折扣上限.将折扣率按从小到大进行排序;
下面进行分类讨论:
(1)若T<最小折扣率的上限,那么最后的价格直接是T*折扣率;
(2)若不够,则选择第二小的折扣率来计算,看其折扣上限与第一
相加是否满足>T,若满足,则将剩余的以第二小的折扣率付钱,
(3)若最后算了所有人的折扣上限加起来小于消费金额T,那么重复(1)和(2),剩余的部分按原价付钱。
(2)代码实现:
#include <algorithm>
#include <iostream>
using namespace std;
int compute(double a[][2], int n, int T)
{
//若所有人折扣的金额加起来小于T
int sum1 = 0, sum = 0, sum2 = 0;
for (int i = 0; i < n; i++)
sum1 += (int)a[i][1];
if (sum1 > T)
{
for (int j = 0; j < n - 1; j++)
{
T -= (int)a[j][1];
if (T > 0)
sum += (int)(a[j][0] * a[j][1]);
int i = j + 1;
if (i < n && T < a[i][1])
sum += (int)(T * a[i][0]);
}
}
else
{
for (int k = 0; k < n; k++)
sum2 += (int)(a[k][1] * a[k][0]);
T = T - sum1;
sum = sum2 + T;
}
return sum;
}
int main()
{
/*cout << "输入总人数和消费的总金额T(以空格隔开):" << endl;*/
int n = 0, T = 0;
;
scanf("%d %d", &n, &T);
double a[100][2]; //初始化
/*cout << "输入每个人的折扣率和折扣上限:" << endl;*/
for (int i = 0; i < n; i++)
{
cin >> a[i][0];
cin >> a[i][1];
}
int sum = 0;
//按照折扣率大小进行排序,在这里选择冒泡排序进行按折扣率大小进行排序,
//即第1列进行排序
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
if (a[j - 1][0] > a[j][0])
{ //若为逆序则交换
double tmp = a[j - 1][0];
a[j - 1][0] = a[j][0];
a[j][0] = tmp; //交换第一列的值
double tmp1 = a[j - 1][1];
a[j - 1][1] = a[j][1];
a[j][1] = tmp1; //交换第二列的值
}
/*
for (int i = 0; i < n; i++)
{
cout << a[i][0] << ",";
cout << a[i][1] << endl;
}
*/
sum = compute(a, n, T);
cout << sum << endl;
system("pause");
return 0;
}
身份证号的校验身份证号码共18位,最后一位是校验位A[18] : aaaaaabbbbbbbbcccd
校验的规则是如下:
前十七位的权值分别是:
x=(A[0]*W[0]+A[1]*W[1]+A[2]*W[2]+...+A[16]*W[16]) mod 11x和校验位y的对应规则对应如下:
y:1 0 x 9 8 7 6 5 4 3 2
若y等于d则身份证号码正确
输出格式:aaaaaabbbbbbbbcccd 正确
若y不等于d则身份证号码不正确
输出格式:应为:aaaaaabbbbbbbbcccy
输入格式:
身份证号码
输出格式:
身份证号码 正确或者不正确输入样例:
52242619811105565x
输出样例:
52242619811105565x 正确