狐狸和绳子的故事

解题思路

升序排列(前提)，把每一个当前的自己都活成最小值，一直向前看，看看自己距离终点有多远(最大绳子个数)

#include <stdio.h>
int main()
{
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);	
		int a[n];
		for(int i=0;i<n;++i)
			scanf("%d",&a[i]);
		//每一个组合中的最小值乘以组合中的绳子个数，就是最大承受重量
		//但是我这种想法如何实现排列呢？n层循环？递归？
		//不，我不会，呜呜。。。
		//
		//换个思路！！！
		//可以先对这n根绳子从小到大排序，
		for(int i=0;i<n;++i)
		{
			for(int j=i;j<n;++j)
			{
				if(a[j]<a[i])
				{
					int temp=a[j];
					a[j]=a[i];
					a[i]=temp;
				}
			}
		}
		//for(int i=0;i<n;++i)printf("%d ",a[i]);
		//每一个组合中的最小值乘以组合中的绳子个数
		//这个最小值可以通过遍历a数组，那绳子个数呢？
		//往前看，比如sample2中，
		//a[0]=1，所有情况有{1},{1,10},{1,15},{1,10,15}
		//a[1]=10,所以情况有{10},{10,1},{10,15},{10,1,15}
		//a[2]=15,所有情况有{15},{15,10},{15,1},{15,1,10}
		//但是有许多重复项
		//观察一下，可以发现，后面出现的重复项都是第一个元素之后有比第一个元素大的元素
		//由此，我们可以先将所有元素升序排序，然后一直向前看就可以啦
		//此时，所谓最大绳子个数，就是看看前方还有多少个元素
		//我们要求的，就是包括当前元素在内的组合&&最大绳子长度(都是排序的功劳，我们才能这样子做)
		int max=a[0];
		for(int i=0;i<n;++i)
		{
			if((a[i]*(n-i))>max)
				max=a[i]*(n-i);
		}
		printf("%d\n",max);

	}
}

题目描述

当年狐狸智斗绳子，换来了生命的重生，心里美滋滋的，尾巴翘的更高了。猎人可谓是机智、勇敢，而这件事情让他颜面扫尽，因此猎人决定夺回面子，再次和狡猾的狐狸一分高下。 大家都知道当年猎人输就输在绳子上面，因此猎人所要做的第一件事情就是从绳子上做文章。 假设一根绳子所能承受的最大的重量为k，若一个物体的重量超过了k，明显这根绳子就会断掉。若将n根绳子扭在一起来吊起一个重量为w的物体，那每根绳子所承受的重量为w/n。 例如：有三根绳子所能承受的最大的重量分别为1N、2N、4N(其中N表示重量的单位牛顿)，那当物体的重量大于3N时第一根绳子就会断掉。计算这三根绳子所能承受的最大的重量就是计算这三根绳子所有的组合中所能承受的最大的重量，这些组合分别为{1}、{2}、{4}、{1、2}、{1、4}、{2、4}、{1，2，4}，当你挑选出其中的一种组合来吊起一个物体时要保证这个组合中的每根绳子都不可断，如{1、4}所能承受的最大的重量为2N，很明显这三根绳子所能承受的最大的重量为4N。 现在的问题是猎人交给你n根绳子，请你帮他计算下这n根绳子所能承受的最大的重量。

Input:
输入的第一行为一个整数t，代表了测试数据的组数。 接下来的每组数据的第一行为一个整数n，表示有n根绳子，第二行为n个整数，代表每根绳子的最大承受重量。

Output:
每组测试数据对应着一个输出，为这n根绳子所能承受的最大的重量。

Sample Input:
2
3
1 2 4
3
1 10 15
Sample Output:
4
20