依图笔试 算法第二套笔试题， AC前三题

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
const int N = 1000 + 10;
int a[N];
int b[N];
int main()
{
	int n;
	cin >> n;
	int idx1 = -1;
	int idx2 = -1;
	for(int i = 0; i < n; ++i)
	{
		cin >> a[i];
		if(a[i] > 0 && idx1 == -1)
		{
			idx1 = i;
		}
	}
	for(int i = 0; i < n; ++i)
	{
		cin >> b[i];
		if(b[i] > 0 && idx2 == -1)
		{
			idx2 = i;
		}
	}

	int ans = 0;
	while(idx1 < n && idx2 < n)
	{
		if(a[idx1] < b[idx2])
		{
			ans += a[idx1] * (idx2 - idx1);
			b[idx2] -= a[idx1];
			idx1 += 1;
		}
		else if(a[idx1] == b[idx2])
		{
			ans += a[idx1] * (idx2 - idx1);
			b[idx2] -= a[idx1];
			idx1 += 1;
			idx2 += 1;
		}
		else
		{
			ans += b[idx2] * (idx2 - idx1);
			a[idx1] -= b[idx2];
			idx2 += 1;
		}
		if(idx1 >= n || idx2 >= n)
			break;
	}
	cout << ans << endl;

}

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
const int N = 10000 + 10;
const int M = 2000000 + 10;
typedef long long ll;
ll a[N];

struct edge 
{
	int v;
	int next;
	ll time;
}e[M];
int head[N];
int cnt = 0;
void add(int u, int v, int t)
{
	e[cnt].v = v;
	e[cnt].time = t;
	e[cnt].next = head[u];
	head[u] = cnt++;
}
ll times[N];
ll cakes[N];

struct node
{
	int fa;
	int u;
	ll time;
	friend bool operator<(const node &a , const node &b)
    {
        return a.time>b.time;   // ascending sort
    }
};

priority_queue<node> q;
void dij(int s, int d)
{
	node cur;

	memset(cakes, 0, sizeof(cakes));
	memset(times, -1, sizeof(times));

	for(int i = head[s]; i != -1;  i = e[i].next)
	{
		node tmp;
		tmp.fa = s;
		tmp.u = e[i].v;
		tmp.time = e[i].time;
		q.push(tmp);
	}
	cakes[s] = a[s];
	times[s] = 0;

	int i = 0;
	while(!q.empty())
	{
		i+=1;
		cur = q.top();
		q.pop();
		//没有走过， 或者有更好的走法
		if(times[cur.u] == -1 || cur.time < times[cur.u])
		{
			times[cur.u] = cur.time;
			cakes[cur.u] = cakes[cur.fa] + a[cur.u];
		}
		// 时间相同，选蛋糕更多的
		else if(cur.time == times[cur.u])
		{
			if(cakes[cur.fa] + a[cur.u] > cakes[cur.u])
				cakes[cur.u] = cakes[cur.fa] + a[cur.u];
			continue;
		}
		else
		{
			continue;
		}
		/* cout << cur.u << " " << cakes[cur.u] << endl; */


		for(int i = head[cur.u]; i != -1; i = e[i].next)
		{
			if(times[e[i].v] != -1 && cur.time + e[i].time > times[e[i].v])
				continue;
			node tmp;
			tmp.fa = cur.u;
			tmp.u = e[i].v;
			tmp.time = cur.time + e[i].time;
			q.push(tmp);
		}
	}
	cout << times[d] << " " << cakes[d] << endl;
}
int main()
{
	int n, m, s, d;
	cin >> n >> m >> s >> d;
	s--;
	d--;
	for(int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	int u, v, t;
	memset(head, -1, sizeof(head));
	for(int i = 0; i < m; ++i)
	{
		cin >> u >> v >> t;
		u--;
		v--;
		add(u, v, t);
		add(v, u, t);
	}

	dij(s, d);

}
//6 80

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
const int N = 10000 + 10;
int cnt[4];
int main()
{
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		x %= 3;
		cnt[x] += 1;
	}

	int ans = cnt[0];
	if(k <= min(cnt[1], cnt[2]))
	{
		ans += k;
	}
	else
	{
		/* ans += k; */
		k -= min(cnt[1], cnt[2]);
		int tmp = min(cnt[1], cnt[2]);
		ans += min(cnt[1], cnt[2]);
		cnt[1] -= tmp;
		cnt[2] -= tmp;

		if(cnt[1] < cnt[2])
		{

			if(cnt[2] / 3 > k)
			{
				ans += k / 2;
			}
			else
			{
				ans += min(cnt[2] / 3, k / 2);
				/* ans -= k; */	

			}
		}
		else// cnt[1] >= cnt[2]
		{
			if(cnt[1] / 3 > k)
			{
				ans += k / 2;
			}
			else
			{
				ans += min(cnt[1] / 3, k / 2);
				/* k -= cnt[1] / 3; */
				/* ans -= k; */
			}
		}
	}

	if(ans < 0)
		ans = 0;

	cout << ans << endl;



}