2015
07-16

# 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.


#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;
}