【独立的牛牛】

小牛牛为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。
一个人生活增加了许多花费: 牛牛每天必须吃一个水果并且需要每天支付x元的房屋租金。
当前牛牛手中已经有f个水果和d元钱,牛牛也能去商店购买一些水果,商店每个水果售卖p元。
牛牛为了表现他独立生活的能力,希望能独立生活的时间越长越好,牛牛希望你来帮他计算一下他最多能独立生活多少天。

输入描述:

输入包括一行,四个整数x,f,d,p(1<=x,f,d,p<=2*10^9),以空格分割

输出描述:

输出一个整数,表示牛牛最多能独立生活多少天。

示例1:
输入

3 5 100 10

输出

11

题目分析

首先计算能保证的房屋能租多少天,如果有剩余再考虑购买水果。

具体代码

#include<iostream>
using namespace std;

int x, f, d, p;
int solve(int x, int f, int d, int p)
{
	int tmp = d / x;
	if (tmp <= f) return tmp;
	d -= f * x;
	return f + d / (x + p);
}
int main()
{
	cin >> x >> f >> d >> p;
	cout << solve(x, f, d, p) << endl;
	return 0;
}

【牛牛吃雪糕】

最近天气太热了,牛牛每天都要吃雪糕。雪糕有一盒一份、一盒两份、一盒三份这三种包装,牛牛一天可以吃多盒雪糕,但是只能吃六份,吃多了就
会肚子疼,吃少了就会中暑。而且贪吃的牛牛一旦打开一盒雪糕,就一定会把它吃完。请问牛牛能健康地度过这段高温期么?

输入描述:

每个输入包含多个测试用例。
输入的第一行包括一个正整数,表示数据组数T(1<=T<=100)。
接下来N行,每行包含四个正整数,表示高温期持续的天数N(1<=N<=10000),一盒一份包装的雪糕数量A(1<=A<=100000),一盒两份包装的雪糕数量B(1<=B<=1
00000),一盒三份包装的雪糕数量C(1<=A<=100000)。

输出描述:

对于每个用例,在单独的一行中输出结果。如果牛牛可以健康地度过高温期则输出"Yes",否则输出"No"。

示例1:
输入:

4
1 1 1 1
2 0 0 4
3 0 2 5
4 24 0 0

输出:

Yes
Yes
No
Yes

题目分析

我们要按照一定的策略来安排这些雪糕来让能撑过的天数最大。
首先我们考虑只吃一盒两份或者一盒三份的雪糕,那么每天我们吃3盒每盒两份的雪糕或者2盒每盒三份的雪糕。接下来用一盒一份的雪糕来填补空隙。空隙从小到大依次是:1盒两份+1盒三份的组合缺1盒一份,2盒两份的组合缺2盒一份,1盒三份的组合缺3盒一份,1盒两份的组合缺4盒一份。按照这个顺序依次填补存在的空隙,剩下来的每盒一份的雪糕,每6盒撑过一天。最后答案取决于能撑过的天数和高温天数的大小比较。

具体代码

#include<iostream>
using namespace std;

int main() {
	int t, n, a, b, c;
	cin >> t;
	while (t--) {
		cin >> n >> a >> b >> c;
		n -= c / 2;
		c = c % 2;
		n -= b / 3;
		b = b % 3;
		if (a >= 1 && b >= 1 && c == 1) {
			a--;
			b--;
			c--;
			n--;
		}
		if (b == 2 && a >= 2) {
			b = 0;
			a -= 2;
			n--;
		}
		if (c == 1 && a >= 3) {
			c = 0;
			a -= 3;
			n--;
		}
		if (b == 1 && a >= 4) {
			c = 0;
			a -= 4;
			n--;
		}
		n -= a / 6;
		a = a % 6;
		if (n > 0)
			printf("No\n");
		else
			printf("Yes\n");
	}
	return 0;
}

【牛牛取快递】

牛牛的快递到了,他迫不及待地想去取快递,但是天气太热了,以至于牛牛不想在烈日下多走一步。他找来了你,请你帮他规划一下,他最少要走多
少距离才能取回快递。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括四个正整数,表示位置个数N(2<=N<=10000),道路条数M(1<=M<=100000),起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。位置编
号从1到N,道路是单向的。数据保证S≠T,保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行,每行包含三个正整数,表示当前道路的起始位置的编号U(1<=U<=N),当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:

对于每个用例,在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

示例1:

输入

3 3 1 3
1 2 3
2 3 3
3 1 1

输出

7

题目分析

实际上题目要求我们分别求出从S到T和从T到S的最短路再把他们加起来。所以我们只要分别以S和T为起点跑单源最短路,再把两次的终点的坐标加起来就可以了。
注意图是有向图。。

具体代码

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct Edge
{
	int dis, to;
	bool friend operator <(Edge x1, Edge x2)
	{
		return x1.dis > x2.dis;
	}
}temp, now;
vector <Edge> vec[10005];
bool life[10005];
int dis[10005], n;
priority_queue <Edge> q;

void init()
{
	for (int i = 1; i <= n; i++)
		dis[i] = 100000000;
	memset(life, 0, sizeof(life));
	while (!q.empty())
		q.pop();
}
int dij(int s, int t)
{
	init();
	temp.to = s;
	temp.dis = 0;
	q.push(temp);
	dis[s] = 0;
	while (!q.empty())
	{
		now = q.top();
		q.pop();
		if (!life[now.to])
		{
			life[now.to] = 1;
			for (int i = 0; i < vec[now.to].size(); i++)
			{
				if (!life[vec[now.to][i].to] && dis[now.to] + vec[now.to][i].dis < dis[vec[now.to][i].to])
				{
					dis[vec[now.to][i].to] = dis[now.to] + vec[now.to][i].dis;
					temp.to = vec[now.to][i].to;
					temp.dis = dis[vec[now.to][i].to];
					q.push(temp);
				}
			}
		}
	}
	return dis[t];
}

int main()
{
	int m, s, t, u, v, d;
	cin >> n >> m >> s >> t;
	while (m--)
	{
		cin >> u >> v >> d;
		temp.dis = d;
		temp.to = v;
		vec[u].push_back(temp);
	}
	printf("%d\n", dij(s, t) + dij(t, s));
	return 0;
}