8 solutions
-
1
题解
就本题的测试案例来看,1 2 3 这三个数有三种不同的操作顺序 1:(1*2+1)3+1=10 2:(13+1)2+1=9 3:(23+1)*1+1=8 从中我们容易发现这样的顺序,如果要求最大值的话,那么每次先用最小的连个数相乘的结果+1,相反,如果要求最小值的话,每次先用最大的两个数相乘的结果+1.这样我们就可以写算法啦
#include <bits/stdc++.h> using namespace std; int a[100005],b[100005]; bool com(int a,int b){ return a>b; } int main(){ int n; while(cin>>n&&n){ for(int i=0;i<n;i++) { cin>>a[i]; b[i]=a[i]; } sort(a,a+n); sort(b,b+n,com); for(int i=1;i<n;i++){ a[i]=a[i]*a[i-1]+1; sort(a+i,a+n); } // for(int i=0;i<n;i++) cout<<a[i]<<endl; for(int i=1;i<n;i++){ b[i]=b[i]*b[i-1]+1; sort(b+i,b+n,com); } // for(int i=0;i<n;i++) cout<<b[i]<<endl; cout<<a[n-1]-b[n-1]<<endl; } return 0; }
-
0
每次取最小的两个数相乘+1最终结果会得到最大值,相反会得到最小值,因此,建立两个数组利用排序分别按从小到大以及从大到小的顺序排列
#include<stdio.h> #include<stdlib.h> #define ll long long //每次取最小的两个数最终可以得到max //每次取最大的两个数最终可以得到min int array[50002]; int attr[50002]; int comp(const void *a,const void *b){ return *(int *)a-*(int *)b; } int comp2(const void *a,const void *b){ return *(int *)b-*(int *)a; } int main(){ int n; int sum; int max; int min; int res; int length; int length2; int len; scanf("%d",&n); for(int i=0; i<n+1; i++){ scanf("%d",&array[i]); attr[i] = array[i]; } length = n; length2 = n; qsort(array,n,sizeof(int),comp);//调用排序函数 for(int i=0; i<n-1; i++){//2 4 5 6 max = array[i]*array[i+1]+1; array[i+1] = max; qsort(&array[i+1],--length,sizeof(int),comp); } qsort(attr,length2,sizeof(int),comp2); for(int i=0; i<n-1; i++){//2 4 5 6 min = attr[i]*attr[i+1]+1; attr[i+1] = min; qsort(&attr[i+1],--length2,sizeof(int),comp2); } printf("%d",max-min); }
-
0
思路
易得从小到大处理得最大值 从大到小处理得最小值 算最大值的时候注意每算一次就要sort一下找到当前数组两最小值,例如数据四个数为3 4 5 6答案应为28 算最小值易得处理出的数肯定最大
代码
#include<bits/stdc++.h> using namespace std; long long a[50005],b[50005]; int main() { int n; scanf("%d",&n); long long max,min; for(int i=0;i<n;i++) { scanf("%lld",&a[i]); b[i]=a[i]; } sort(a,a+n); sort(b,b+n); for(int i=0;i<n-1;i++)//max { a[i+1]=a[i]*a[i+1]+1; sort(a,a+n); } max=a[n-1]; for(int i=n-1;i>0;i--)//min { b[i-1]=b[i]*b[i-1]+1; } min=b[0]; printf("%lld",max-min); return 0; }
-
0
题目分析:
首先,这题我们可以知道,擦掉的数组元素顺序不同,最后剩的值的大小也不同。
所以我们现在需要确定的是我们要怎么才能得到最小值和最大值
由其他dalao的题解得出:
每次删两个最大的得到的是最小值
每次删两个最小的得到的是最大值
实在想知道证明过程可以点这个链接:https://blog.csdn.net/niuox/article/details/8524457
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n; int a[5003],b[5003]; bool cmp1(int x,int y) { return x > y; } bool cmp2(int x,int y) { return x < y; } int main() { scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d",&a[i]); b[i] = a[i]; } int x1 = n,x2 = n; while(x1 > 2) { sort(a + 1,a + x1 + 1,cmp1); a[x1 - 1] = a[x1 - 1] * a[x1] + 1; x1--; } while(x2 > 2) { sort(b + 1,b + x2 + 1,cmp2); b[x2 - 1] = b[x2 - 1] * b[x2] + 1; x2--; } printf("%d",a[1] * a[2] - b[1] * b[2]); return 0; }
-
0
将数字存入数组,题目需要经过a*b+1运算后的最大值和最小值。我们讲数组倒序排列,先将大的值去掉剩下小的值,这样经过运算后就得到最小值。同理最大值就将数组顺序排列运算,注意的是经过运算产生新的值会使数组顺序发生变化,所以我们需要在循环里面再排序. #include #include #include<stdio.h> using namespace std; int a[50005],b[50005]; int cmp(int a,int b){ return a>b; } int main(){ int n,max,min; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; } sort(a+1,a+1+n,cmp); for(int i=2;i<=n;i++) a[i]=a[i]*a[i-1]+1; min=a[n]; sort(b+1,b+1+n); for(int i=2;i<=n;i++){ b[i]=b[i]*b[i-1]+1; sort(b+1,b+n+1); } max=b[n]; printf("%d\n",max-min); return 0; }
-
0
P1091. 「一本通 1.1 练习 1」数列极差
题意概述
我们可以将题中的任意两个数 a、b 擦除,并且插入 (a*b + 1) ,直到只剩下一个数。 不同擦除方法可以得到很多数字这样的数字,求出其中的max和min的差值。
题意分析
我们可以知道,要使得数字最大或者最小肯定是有一定规律的。 我们列举一下:
1 2 3 顺着乘下去得到的结果是:9 3 2 1 顺着乘下去得到的结果是:7 其实这里可以看出
越大的数字留在后面,那么结果会越大. 越小的数字留在越后面,结果会越小
好的,到这里我们已经快要接近真相了。是否,对数列排序后就可以直接往后乘了呢???建议停下来想想
我们再来看一组数据
1 2 3 3 4 前三个得到的结果是 9 ,接下来的数列按照:9 3 4 继续? 必然这是不行的 对于这种情况我们就要对数列不断的排序,以保证得到最优解。
总结一下:
max的计算过程中保证数列一直处于降序. min的计算过程中保证数列一直处于升序
可行代码
废话完了,上代码
#include <algorithm> #include <iostream> using namespace std; int n, a[11], b[11]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i]; sort(a + 1, a + n + 1); for (int i = 2; i <= n; i++) a[i] = a[i] * a[i - 1] + 1, sort(a + 1, a + n + 1); sort(b + 1, b + n + 1, greater<int>()); for (int i = 2; i <= n; i++) b[i] = b[i] * b[i - 1] + 1; cout << a[n] - b[n] << endl; }
END 加油吧,刷题刷到裂开^-^
-
0
题目解析:
每次将最小的两个值进行处理直到剩下最后一个数,就是极大值;每次将最大的两个值进行处理直到剩下最后一个数,就是极小值。本题的关键是排序,将数组从小到大排序,取前a[1]a[2]两个数进行处理,然后将新的值赋值到a[2],a[1]=0,再重新排序,0肯定在a[1],所以取a[2]a[3]处理,以此类推,直到只余下a[n]就是极大值。极小值的求法同理,只不过默认的是从小到大排序,所以求极小值时应该逆序取值,每次都取b[n]b[n-1]处理,直到只余下b[n]即极小值。
参考代码:
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int a[N],b[N]; int main(){ int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i]; } sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); for(int i = 1; i <= n - 1; i++) { a[i + 1] = a[i] * a[i + 1] + 1; a[i] = 0; sort(a + 1, a + n + 1); } for(int i = 1; i <= n - 1; i++) { int t = n; b[t - 1] = b[t] * b[t - 1] + 1; b[t] = 0; sort(b + 1, b + n + 1); } cout << a[n] - b[n]; return 0; }
- 1
Information
- ID
- 95
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 146
- Accepted
- 52
- Uploaded By