ubuntu 12.04 android编译环境配置

简单总结题意:

有一个数组,数组中的数值不会大于4,即只能是1,2,3,4,要把这些数值装进一个容量最大为4的容器里面,使得所用到这样的容器的个数最小。


经测试数据很大,会有10万个数据,所以这里我并不用排序数据,而是使用counting sort的思想,根据特定的数据优化,使得题解时间复杂度为O(n)。

程序如下:


#include <iostream>
#include <vector>
#include <string>
#include <ctype.h>

using namespace std;

void Taxi()
{
	int n = 0;
	cin>>n;
	int nums = 0;
	int A[3] = {0};
	int a = 0;
	for (int i = 0; i < n; i++)
	{
		cin>>a;
		if (4 == a) nums++;
		else A[a-1]++;
	}

	nums += A[1] / 2;
	A[1] %= 2;

	if (A[0] <= A[2]) 
	{
		nums += A[0];
		A[2] -= A[0];
		if (A[1]) nums++;
		nums += A[2];
	}
	else
	{
		nums += A[2];
		A[0] -= A[2];
		nums += A[0] / 4;
		A[0] %= 4;
		if (A[1])
		{
			A[0] -= 2;
			nums++;
		}
		if (A[0] > 0) nums++;
	}

	cout<<nums;
}

题目出处:

http://codeforces.com/problemset/problem/158/B

ubuntu 12.04 android编译环境配置,布布扣,bubuko.com

ubuntu 12.04 android编译环境配置

上一篇:android—Intent发送文本email


下一篇:ios--OpenCV--基于模板图片的标记识别