高精度整数

实现


#ifndef ACM_BIG_NUMBER__H_
#define ACM_BIG_NUMBER__H_
#include <string>

高精度整数
	任务: 完成高精度整数的加减乘除以及取摸运算
	注意: 运算过程中和结果都不能包含负数
	说明: d[0]表示数字在压缩后的总位数 d[i]表示第i位上的数(每4位压缩成一个万进制数位)
	      例如: "9876543210"的内部表示: d[0]=3, d[1]=3210, d[2]=7654, d[3]=98
	构造函数: BigNumber[string s] 从字符串s构造
	成员函数: string toString() 输出为字符串
	重载运算符: +,-,*,/,<,==       

using std::string;
const int ten[4] = { 1,10,100,1000 };
const int maxl = 1000; //最大位数 最多可以表示的数字长度为 4*maxl-4

class BigNumber {
public:
	int d[maxl];
public:
	BigNumber() {
		*this = BigNumber(string("0"));
	}
	BigNumber(const string& s) {
		int len = s.size();
		d[0] = (len - 1) / 4 + 1;
		int i, j, k;
		for (i = 1; i < maxl; ++i) d[i] = 0;
		for (i = len - 1; i >= 0; --i) {
			j = (len - i - 1) / 4 + 1;
			k = (len - i - 1) % 4;
			d[j] += ten[k] * (s[i] - '0');
		}
		while (d[0] > 1 && d[d[0]] == 0) --d[0];
	}

	string toString() {
		string s("");
		int i, j, temp;
		for (i = 3; i >= 1; --i)
			if (d[d[0]] >= ten[i]) break;
		temp = d[d[0]];
		for (j = i; j >= 0; --j) {
			s = s + (char)(temp / ten[j] + '0');
			temp %= ten[j];
		}
		for (i = d[0] - 1; i > 0; --i) {
			temp = d[i];
			for (j = 3; j >= 0; --j) {
				s = s + (char)(temp / ten[j] + '0');
				temp %= ten[j];
			}
		}
		return s;
	}

}zero("0"),d,temp,midl[15]; // d充当除法时的余数

//重载大数乘法
BigNumber operator*(const BigNumber& a, const BigNumber& b) {
	BigNumber c;
	c.d[0] = a.d[0] + b.d[0];

	int i, j, x;
	for (i = 1; i <= a.d[0]; ++i) {
		x = 0;
		for (j = 1; j <= b.d[0]; ++j) {
			x = a.d[i] * b.d[j] + x + c.d[i + j - 1];
			c.d[i + j - 1] = x % 10000;
			x /= 10000;
		}
		c.d[i + b.d[0]] = x;
	}

	while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
		--c.d[0];
	return c;
}

//重载大数加法
BigNumber operator + (const BigNumber& a, const BigNumber& b) {
	BigNumber c;
	c.d[0] =(a.d[0]>=b.d[0]?a.d[0]:b.d[0]);
	int i, x = 0;
	for (i = 1; i <= c.d[0]; ++i) {
		x = a.d[i] + b.d[i] + x;
		c.d[i] = x % 10000;
		x /= 10000;
	}
	while(x!=0) {
		c.d[++c.d[0]] = x % 10000;
		x /= 10000;
	}
	return c;
}

//重载大数减法 注意:只能大数减去小数
BigNumber operator - (const BigNumber& a, const BigNumber& b) {
	BigNumber c;
	c.d[0] = a.d[0];
	int i, x = 0;
	for (i = 1; i <= c.d[0]; ++i) {
		x = 10000 + a.d[i] - b.d[i] + x;
		c.d[i] = x % 10000;
		x = x / 10000 - 1;
	}

	while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
		--c.d[0];
	return c;
}

// helper func
bool __smaller(const BigNumber& a, const BigNumber& b,int delta) {
	if (a.d[0] + delta != b.d[0])
		return a.d[0] + delta < b.d[0];
	int i;
	for (i = a.d[0]; i > 0; --i)
		if (a.d[i] != b.d[i + delta])
			return a.d[i] < b.d[i + delta];
	return true;
}
// helper func
void __Minus(BigNumber& a, const BigNumber& b, int delta) {
	int i, x = 0;
	for (i = 1; i <= a.d[0] - delta; ++i ) {
		x = 10000 + a.d[i + delta] - b.d[i] + x;
		a.d[i + delta] = x % 10000;
		x = x / 10000 - 1;
	}
	while ((a.d[0] > 1) && (a.d[a.d[0]] == 0))
		--a.d[0];
}

//重载大数除法
BigNumber operator / (const BigNumber& a, const BigNumber& b) {
	BigNumber c;
	d = a;
	int i, j, temp;
	midl[0] = b;
	for (i = 1; i <= 13; ++i) {
		midl[i] = midl[i - 1] * BigNumber("2");
	}

	for (i = a.d[0] - b.d[0]; i >= 0; --i) {
		temp = 8192;
		for (j = 13; j >= 0; --j) {
			if (__smaller(midl[j], d, i)) {
				__Minus(d, midl[j], i);
				c.d[i + 1] += temp;
			}
			temp /= 2;
		}
	}
	c.d[0] = (1 >= a.d[0] - b.d[0] + 1 ? 1 : a.d[0] - b.d[0] + 1);
	while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
		--c.d[0];
	return c;
}

// 重载 '<'
bool operator < (const BigNumber& a, const BigNumber& b) {
	if (a.d[0] != b.d[0])
		return a.d[0] < b.d[0];
	int i;
	for (i = a.d[0]; i > 0; --i)
		if (a.d[i] != b.d[i])
			return a.d[i] < b.d[i];
	return false;
}
   
// 重载 '=='
bool operator == (const BigNumber& a, const BigNumber& b) {
	int i;
	if (a.d[0] != b.d[0]) return false;  
	for (i = 1; i <= a.d[0]; ++i)     
		if (a.d[i] != b.d[i])     
			return false;     
	return true;  
}

#endif

测试

#include "上述代码组成的头文件"

#include <iostream>
#include <cassert>

using namespace std;

int main() {
	
	string src1 = "1310";
	string src2 = "10";
	BigNumber ins_1(src1);
	BigNumber ins_2(src2);
	BigNumber ins_3("1310");
	
	assert((ins_1 + ins_2).toString() == "1320");
	assert((ins_1 * ins_2).toString() == "13100");
	assert((ins_1 - ins_2).toString() == "1300");
	assert((ins_1 / ins_2).toString() == "131");
	assert((ins_1 < ins_2) == false);
	assert((ins_1 == ins_3) == true);
}

区间调度系列

ref https://blog.csdn.net/yutianzuijin/article/details/78897604

背景知识

假设区间是闭合的，并定义为[start,end]。我们首先看一下区间重叠的定义。给定两个区间[s1,e1]和[s2,e2]，它们重叠的可能性有四种：

可以看出，如果直接考虑区间重叠，判断条件比较复杂，我们从相反的角度考虑，考虑区间不重叠的情况。区间不重叠时的判断条件为：

也即：(e1<s2||s1>e2)，所以区间重叠的判断条件为：

最多区间调度问题

定义:数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。
例如:下面例子中有5个任务，每个任务两端分别是其任务的开始时间和结束时间，怎么选择可以使参与的任务数最多，也就是被选择的区间(1个任务对应一个区间)最多?

算法:在可选的工作中，每次都选取结束时间最早的工作。因此，将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。


#include <algorithm>
#include <utility> // pair<T1,T2>

const int  MAXN=10000;	
int N, S[MAXN], T[MAXN]; 

pair<int, int> itv[MAXN];

void solve() {
	//对pair进行的是字典序比较，为了让结束时间早的工作排在前面，把T存入first，把S存入second
	for (int i = 0; i<N; i++){
		itv[i].first  = T[i];
		itv[i].second = S[i];
	}

	sort(itv, itv + N);

	//t是最后所选工作的结束时间
	int ans = 0, t = 0;
	for (int i = 0; i<N; i++){
		if (t<itv[i].second){ //判断区间是否重叠
			ans++;
			t = itv[i].first;
		}
	}

	printf("%d\n", ans);
}