我的OJ草稿纸

#include <string>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <float.h>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include<functional>
#include <vector>
using namespace std;

//第132题. 加油站，优先队列。可加之油加最少次数到达目的地
struct oilAdder {
	int distance;
	int value;
	bool inQueue;
	//重载<运算符，放到优先队列中会大value排在队首，本题没有用到
	bool operator<(const oilAdder& a) const
	{
		return value < a.value;
	}
};
void addOil()
{
	int n;
	cin >> n;
	vector<oilAdder> v;
	for (int i = 0; i < n; i++)
	{
		oilAdder input;
		cin >> input.distance;
		cin >> input.value;
		input.inQueue = false;
		v.push_back(input);
	}
	int l, p;
	cin >> l >> p;
	if (p >= l)
	{
		cout << "0";
		return;
	}
	int result = 0;
	priority_queue<int> q;
	while (p < l)
	{
		for (int j = 0; j < v.size(); j++)
		{
			if (l - v[j].distance <= p && v[j].inQueue == false)
			{
				q.push(v[j].value);
				v[j].inQueue = true;
			}
		}
		if (q.empty())
		{
			cout << "-1";
			return;
		}
		p += q.top();
		q.pop();
		result++;
	}
	cout << result;
}
struct mypair {
	int key;
	int value;
	mypair(int a, int b) {
		key = a;
		value = b;
	}
	//重载<运算符
	bool operator<(const mypair& a) const
    {
		        return key < a.key; //大顶堆
	}
};
//方法2
 struct tmp2 //重写仿函数
 {
	     bool operator() (mypair a, mypair b)
		     {
		         return a.key < b.key; //大顶堆
		     }
};
void testPriorityQueue()
{

	//默认大顶堆
	priority_queue<int> q;
	//小顶堆, greater<int>是functional库中实现的一个防函数，实际是一个类，实现了比较，看起来像函数
	priority_queue<int, vector<int>, greater<int> > c;
	for (int i = 0; i < 5; i++)
	{
		q.push(i);
		c.push(i);
	}
	for (int i = 0; i < 5; i++)
	{
		cout << q.top() << endl;
		q.pop();

	}
	for (int i = 0; i < 5; i++)
	{
		cout << c.top() << endl;
		c.pop();

	}
	mypair p1(1,2);
	mypair p2(2,3);
	mypair p3(4, 5);
	mypair p4(4, 9);
	//自定义大顶堆1
	priority_queue<mypair> mq;
	//自定义大顶堆2
	priority_queue<mypair, vector<mypair>, tmp2> f;
	mq.push(p1);
	mq.push(p2);
	mq.push(p3);
	mq.push(p4);
	for (int i = 0; i < 4; i++)
	{
		cout << mq.top().key << " " << mq.top().value << endl;
		mq.pop();
	}
	//pair对，先比较第一个元素，在比较第二个元素，默认就是大顶堆
	    priority_queue<pair<int, int> > a;
	     pair<int, int> b(1, 2);
	    pair<int, int> cc(1, 3);
	     pair<int, int> d(2, 5);
	    a.push(d);
	    a.push(cc);
	    a.push(b);
	  while (!a.empty())
		{
			cout << a.top().first << ' ' << a.top().second << '\n';
			a.pop();
		}
}

//532. 字符串编码, 递归、字符串操作、set和vector数据结构使用
typedef struct {
	string key;
	string value;
}Rule;
vector<Rule> v;
void codec(string src,string tar,set<string>&output)
{
	int len = src.length();
	if (len == 0)
	{
		output.insert(tar);
	}
	for (int i = 1; i <= len; i++)
	{
		string tmp = src.substr(0, i);
		for (int j = 0; j < v.size(); j++)
		{
			if (v[j].key == tmp)
			{
				codec(src.substr(i, len), tar + v[j].value, output);
			}
		}
	}
}

bool cmp(string a, string b)
{
	return a.compare(b) < 0;
}

void stringCodec()
{
	string src, target;
	cin >> src >> target;
	string key, value;
	while (cin >> key >> value)
	{
		if (value == "1")
		{
			break;
		}
		Rule rule;
		rule.key = key;
		rule.value = value;
		v.push_back(rule);
	}
	set<string>output;
	codec(src, "", output);
	set<string>::iterator it = output.begin();
	int index = 1;
	while (it!= output.end())
	{
		if ((*it).compare(target) == 0)
		{
			cout << index;
			return;
		}
		it++;
		index++;
	}
	cout << "-1";
}

//第124题，括号匹配，栈的使用
void stackTest()
{
	for (int i = 0; i < 6; i++)
	{
		string str;
		cin >> str;
		stack<char> s;
		bool flag = true;
		for (int j = 0; j < str.length(); j++)
		{
			char tmp = str[j];
			if (tmp == '(' || tmp == '[' || tmp == '{' || tmp == '<')
			{
				s.push(tmp);
			}
			else
			{
				if (s.empty())
				{
					flag = false;
					break;
				}
				char top = s.top();
				s.pop();
				if ((top == '(' &&tmp!=')')||(top=='{'&&tmp!='}')||(top=='['&&tmp!=']')||(top=='<'&&tmp!='>'))
				{
					flag = false;
					break;
				}
			}
		}
		if (flag == false || !s.empty())
		{
			cout << "no" << endl;
			continue;
		}
		cout << "yes" << endl;
	}
}


//第134题linkedList，模拟链表操作 2019-09-19
struct node {
	int value;
	struct node* next;
};

node *head, *p;
int listLen = 0;

void insert(int a, int b) {
	p = head;

	node *newNode = new node;
	newNode->value = b;
	if (listLen == 0)
	{
		head = newNode;
		head->next = NULL;
		listLen++;
		return;
	}
	if (a == 0)
	{
		newNode->next = p;
		head = newNode;
		listLen++;
		return;
	}
	int curPos = 1;
	while (curPos != a)
	{
		curPos++;
		p = p->next;
	}
	if (curPos == listLen)
	{
		newNode->next = NULL;
		p->next = newNode;
		listLen++;
		return;
	}
	newNode->next = p->next;
	p->next = newNode;
	listLen++;
}

void init(int param[], int len) {
	int pos = 0;
	for (int i = 0; i < len; i++)
	{
		insert(pos++, param[i]);
	}
}

void erase(int position)
{
	p = head;
	if (position >= listLen) {
		return;
	}
	if (position == 0)
	{
		head = p->next;
		listLen--;
		delete p;
		return;
	}
	int curPos = 1;
	while (curPos != position)
	{
		p = p->next;
		curPos++;
	}
	node *toDelete = p->next;
	p->next = toDelete->next;
	delete toDelete;
	listLen--;
}

void linkedList() {
	int n, q;
	scanf("%d%d", &n, &q);
	int input[100005];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &input[i]);
	}
	init(input, n);
	for (int j = 0; j < q; j++)
	{
		int type;
		scanf("%d", &type);
		if (type == 1)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			insert(a, b);
		}
		else
		{
			int a;
			scanf("%d", &a);
			erase(a-1);
		}
	}
	for (node * iterator = head; iterator != NULL; iterator = iterator->next)
	{
		printf("%d ", iterator->value);
	}
}


void test() {
	string str;
	getline(cin, str);
	int param[] = { 1,2,3 };
	int *p = new int[3];
	int p2[5];
	p2[0] = 1;
	p2[1] = 2;
	cout << str << " "<< sizeof(param)<<"  "<<sizeof(p)<<" "<<sizeof(p2)<<endl;
}

//第31题，整数拆分
void integerDevide2() {
	int n;
	while (scanf("%d", &n)!=EOF) {
		int ret[125][125] = { 0 };
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				if (i == 1 || j == 1) {
					ret[i][j] = 1;
				}
				else if (i == j) {
					ret[i][j] = ret[i][j - 1] + 1;
				}
				else if (i - j < j) {
					ret[i][j] = ret[i][j - 1] + ret[i - j][i - j];
				}
				else {
					ret[i][j] = ret[i][j - 1] + ret[i - j][j];
				}
			}
		}
		printf("%d\n", ret[n][n]);
	}
}

int split(int n, int m) {
	if (n < 1 || m < 1) {
		return 0;
	}
	if (n == 1 || m == 1) {
		return 1;
	}
	if (n < m) {
		return split(n, n);
	}
	if (m == n) {
		return split(n, m - 1) + 1;
	}
	if (m < n) {
		return split(n, m - 1) + split(n - m, m);
	}
}

void integerDevide(){
	int n;
	while (scanf("%d", &n)) {
		int result = split(n, n);
		printf("%d\n", result);
	}
}

//第270题， 求两数和为100的数对数
void addSumIs100() {
	int n;
	scanf("%d", &n);
	int list[100005];
	map<int, int> m;
	map<int, int>::iterator it;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &list[i]);
		it = m.find(list[i]);
		m[list[i]] = it == m.end() ? 1 : it->second + 1;
	}
	int result = 0;
	map<int, int>::iterator it_search;
	for (it = m.begin(); it != m.end(); it++)
	{
		it_search = m.find(100 - it->first);
		if (it->first == 50)
		{
			int value = it->second;
			result += value* (value - 1);
		}
		else
		{
			if (it_search != m.end())
			{
				result += it->second * it_search->second;
			}
		}
	}
	cout << result/2;
}

//学习map的基本使用
void testLanguage() {
	string key = "name";
	int value = 123;
	pair<string, int> p(key, value);
	cout << p.first << " is " << p.second << endl;
	map<string, int> m;
	m.insert(p);
	m["age"] = 18;
	map<string, int>::iterator it = m.find("age");
	if(it != m.end())
	{
		cout << it->first << " is " << it->second << endl;
	}
	m.erase(it);
	m.erase("name");
	m.insert(pair<string, int>("a", 3));
	m.insert(make_pair<string, int>("b", 4));
	for (map<string, int>::iterator it = m.begin(); it != m.end(); it++)
	{
		cout << it->first << " is " << it->second << endl;
	}
}

//第24题，求数列和
void sumOfSequence() {
	int a, n, k;
	scanf("%d%d%d", &a, &k, &n);
	int sum = (a + a + n * k) * (n + 1) / 2;
	printf("%d", sum);
}

//第13题，打印表格
void printOdd(int m) {
	for (int i = 0; i < m; i++)
	{
		cout << "+" << "---";
	}
	cout << "+";
}

void printEven(int m) {
	for (int i = 0; i < m; i++) {
		cout << "|" << "   ";
	}
	cout << "|";
}

void ThirdTeen()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		printOdd(m);
		cout << endl;  
		printEven(m);
		cout << endl;
	}
	printOdd(m);
}


//第9题，连续m个整数表示n
bool isTrue(int n, int m)
{
	float k = (float)2 * n / m - m + 1;
	cout << k << endl;
	double err = 1e-10; //先自己定义误差
	if (abs(int(k) - k) <= err  && (int)k % 2 == 0 && (int)k > 0) {
		return true;
	}
	return false;
}

void nine() {

	//please define the C++ input here. For example: int a,b; cin>>a>>b;;

	//please finish the function body here.

	//please define the C++ output here. For example:cout<<____<<endl;
	int n;
	scanf("%d", &n);
	for (int i = 2; i<n; i++) {
		if (isTrue(n, i)) {
			cout << "YES";
			return;
		}
	}
	cout << "NO";
	return;
}

//第7题，计算平均每个单词长度
void avg_word_count_7() {
	/*char str[101];
	scanf("%[^\n]", &str);
	printf("%s", str);*/
	string str;
	getline(cin, str);
	int wordCount = 1;
	int totalLen = 0;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] != ' ') {
			totalLen++;
		}
		else
		{
			wordCount++;
		}
	}
	cout <<fixed<< setprecision(2)<< totalLen* 1.0 / wordCount << endl;
}


int main()
{
	addOil();
	//testPriorityQueue();
	//stringCodec();
	//stackTest();
	//linkedList();
	//test();
	//addSumIs100();
	//testLanguage();
	//sumOfSequence();
	//ThirdTeen();
	//nine();
	//avg_word_count_7();
	//char *p = "ss";
	//cout << p << endl;
	//cout << 34 << endl;
	//cout << sizeof(int) << endl;
	//cout << sizeof(string) << endl;
	//string a = "ss";
	//char * p;
	//p = (char *)a.c_str();
	//cout << p[0]<< p[1] << endl;
	//char * p = "white.bmp";
	//char * b = new char[3];
	//char b2[3] = {'a','b','c'};
	//cout << sizeof(b2) <<"ss"<< endl;
	//int len = strlen(p);
	//for (int i = len - 3, j = 0; i < len; i++, j++) {
	//	b[j] = p[i];
	//}
	//cout << string(b) << endl;
	//cout << strncpy(b, p + strlen(p) - 3, 3) << endl;
	system("pause");
    return 0;
}