8 solutions

  • 1
    @ 2021-10-18 1:19:17

    题解

    就本题的测试案例来看,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
      @ 2022-2-16 21:47:47

      每次取最小的两个数相乘+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
        @ 2021-10-18 0:08:24

        思路

        易得从小到大处理得最大值 从大到小处理得最小值 算最大值的时候注意每算一次就要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
          @ 2021-10-17 17:35:07

          题目分析:

          首先,这题我们可以知道,擦掉的数组元素顺序不同,最后剩的值的大小也不同。

          所以我们现在需要确定的是我们要怎么才能得到最小值和最大值

          由其他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
            @ 2021-10-17 16:05:29

            将数字存入数组,题目需要经过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
              @ 2021-10-17 0:36:37

              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
                @ 2021-10-16 19:18:55

                题目解析:

                每次将最小的两个值进行处理直到剩下最后一个数,就是极大值;每次将最大的两个值进行处理直到剩下最后一个数,就是极小值。本题的关键是排序,将数组从小到大排序,取前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;
                }
                
                • 0
                  @ 2021-10-14 20:38:02

                  最大值应该是每次把最小的两个数相乘,直到只剩一个数,最小值是每次把最大的两个数相乘,直到只剩一个数,但是注意,这里最大和最小的应该是实时的,每次计算完,应该重新排序,找出最大和最小

                  • 1

                  Information

                  ID
                  95
                  Time
                  1000ms
                  Memory
                  256MiB
                  Difficulty
                  5
                  Tags
                  # Submissions
                  149
                  Accepted
                  53
                  Uploaded By