fork download
copy 
  1. #include<stdio.h>
  2. #include<malloc.h>
  3. void merge(int *A,int left,int mid,int right)
  4. {
  5. 	int i,j,tempmid=mid+1,l=left,r=right;
  6. 	int *temp;
  7. 	temp=(int*)malloc(sizeof(int)*(right-left+1));
  8. 	for(i=0;i<(right-left+1);i++)
  9. 	{
  10. 		if(l<=mid && tempmid<=r)
  11. 		{
  12. 			if(A[l]<A[tempmid])
  13. 			{
  14. 				temp[i]=A[l];
  15. 				l++;
  16. 			}
  17. 			else
  18. 			{
  19. 				temp[i]=A[tempmid];
  20. 				tempmid++;
  21. 			}
  22. 		}
  23. 		else
  24. 		{
  25. 			if(l>mid)
  26. 			{	
  27. 				temp[i]=A[tempmid];
  28. 				tempmid++;
  29. 			}
  30. 			else if(tempmid>right)
  31. 			{
  32. 				temp[i]=A[l];
  33. 				l++;
  34. 			}
  35. 		}
  36. 	}
  37. 	j=0;
  38. 	for(i=left;i<=right;i++,j++)
  39. 		A[i]=temp[j];
  40. 	free(temp);
  41. }
  42.  
  43. void mergesort(int *A,int left,int right)
  44. {
  45. 	int mid;
  46. 	mid=(left+right)/2;
  47. 	if(left<right)
  48. 	{
  49. 		mergesort(A,left,mid);
  50. 		mergesort(A,mid+1,right);
  51. 		merge(A,left,mid,right);
  52. 	}
  53. 	else
  54. 		return;
  55. }
  56.  
  57. main()
  58. {
  59. 	int party[1000],t,i,m,n,num,count=0,maj,req=0;
  60. 	scanf("%d",&t);
  61. 	while(t)
  62. 	{
  63. 		count=0,req=0;
  64. 		for(i=0;i<1000;i++)
  65. 			party[i]=0;
  66. 		scanf("%d%d",&m,&n);
  67. 		for(i=0;i<n;i++)
  68. 		{
  69. 			scanf("%d",&num);
  70. 			party[num]++;
  71. 		}
  72. 		mergesort(party,0,m);
  73. 		/*for(i=0;i<=m;i++)
  74. 			printf("%d ",party[i]);*/
  75. 		maj=(n/2)+1;
  76. 		while(count<maj)
  77. 		{
  78. 			count+=party[m];
  79. 			m--;
  80. 			req++;
  81. 		}
  82. 		printf("%d\n",req);
  83. 	t--;
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 2384KB
comments (?)
stdin
copy 
2
6 10
1 2 3 1 0 4 5 3 1 4 
3 6
1 2 2 0 2 2
stdout
copy 
3
1
https://ideone.com/3wKZuH
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!