首页 > ACM题库 > HDU-杭电 > HDU 4476-Cut the rope-枚举-[解题报告]HOJ
2015
07-16

HDU 4476-Cut the rope-枚举-[解题报告]HOJ

Cut the rope

问题描述 :

  Now we have some ropes. For each rope, you can cut it only once at any place, or you can also do nothing on it.
  If we cut these ropes optimally, how many ropes we can get at most with the same length?

输入:

  There is an integer T (1 <= T <= 100) in the first line, indicates there are T test cases in total.
  For each test case, the first integer N (1 <= N <= 100000) indicates there are N ropes. And then there are N integers whose value are all in [1, 100000], indicate the lengths of these ropes.

输出:

  There is an integer T (1 <= T <= 100) in the first line, indicates there are T test cases in total.
  For each test case, the first integer N (1 <= N <= 100000) indicates there are N ropes. And then there are N integers whose value are all in [1, 100000], indicate the lengths of these ropes.

样例输入:

3
1 1
2 1 2
3 2 3 3

样例输出:

2
3
5
Hint
  For Sample 1, we can get two ropes with 0.5 unit length.   For Sample 2, we can get three ropes with 1 unit length.   For Sample 3, we can get five ropes with 1.5 unit length.

题目:给n跟绳子,每条绳子你可以在任何位置把它切成两条,或者不切,问最大有多少根绳子的长度一样

分析:暴力了一次 ,TLE,然后就想O(n)的算法,想的是,把所有的绳子的长度都乘以2,就不会出现小数了,然后对每一条绳子的长度能够切出最大的数目:从这条绳子到最后一条绳子的个数+这个条绳子长度二倍的绳子的个数;每条绳子到最后一条绳子的长度的个数,只需先扫描一遍就可以了;设一个结构体,有两个元素,arr[i].flag长度为i的绳子个数为arr[i].flag,    arr[i].c代表从第一条绳子到长度为i的绳子个数,

代码:

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
const int con=500000;
struct node
{
    int flag;
    int c;
}arr[con];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        memset(arr,0,sizeof(arr));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            arr[x*2].flag++;
        }
        int c=0;
        for(int i=1;i<=200000;i++)
        {
            if(arr[i].flag!=0)
            {
                c+=arr[i].flag;
                arr[i].c=c;
            }
            else
                arr[i].c=c;
        }
        int ans=0;
        for(int i=1;i<=200000;i++)
        {
            int temp=0;
            temp=n-arr[i].c+arr[i].flag+arr[i*2].flag;
            if(temp>ans)
                ans=temp;
        }
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wconvey/article/details/8247407