依图笔试 算法第二套笔试题， AC前三题
第一题，收费站， 用的双指针, 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;
}
第二题，时间最短，蛋糕最多，用的dijstkra, AC
#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
第三题，统计3的个数， 将数字%3，余数为0，1，2， 只需对余数为1和2的数组进行相加。AC
#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;
}
