DAY2 模拟考试第三题 情书的代价

3、情书的代价
（cost.pas/c/c++）
【题目描述】

【输入格式】

【输出格式】

【样例输入】
3 5
2 3 4
1 3
3 2
【样例输出】
3
【数据规模】

``````#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;
#define maxn 500005
#define LL unsigned long long
LL n,ans,rest,num_e,t;
struct edge{
LL to,nex;
}e[maxn];
bool v[maxn];
rd[y]++;
}
if(rest>=cost[x]) rest-=cost[x];
else{
ans++;
rest=t-cost[x];
}
}
queue<LL> q;
int main(){
freopen("cost.in","r",stdin);
freopen("cost.out","w",stdout);
scanf("%llu%llu",&n,&t);
for(LL i=1;i<=n;i++) scanf("%llu",&cost[i]);
LL a,b;

for(LL i=1;i<=n;i++){
if(!rd[i]) q.push(i),v[i]=1;
}
while(!q.empty()){
LL x=q.front();q.pop();
if(!v[e[i].to]){
q.push(e[i].to);
v[e[i].to]=1;
}
}
}
printf("%llu",ans);
return 0;
}``````

``````#include<cstdio>
using namespace std;
int n, limit, x, y;
int t[35], ans;
int mem[35][35];
int f[35][35], size[35], topo[35], in[35];
int w[35][35], Size[35];
int q[35], front, rear;
void maketopo()
{
front = 1; rear = 1;
for(int i = 1; i <= n; i++) if(in[i] == 0) q[rear++] = i;
while(front < rear)
{
int u = q[front]; front++;
for(int i = 1; i <= size[u]; i++)
{
in[f[u][i]]--;
if(in[f[u][i]] == 0) q[rear++] = f[u][i];
}
}
topo[0] = 0;
for(int i = 1; i <= n; i++) topo[q[i]] = i;
return;
}
bool vis[35];
void dfs(int day, int use, int pre)
{
int finish = 0;
for(int i = 1; i <= n; i++) if(!vis[i]) { finish = i; break; }
if(finish == 0){
if(day<ans) ans=day;
return;
}
int tot = 0;
for(int i =finish; i <= n; i++) if(! vis[i]) tot += t[i];
if(day + tot / limit >= ans) return;
bool canfinish = false;
for(int i = finish; i <= n; i++) if(! vis[i])
{
bool ok = true;
for(int j = 1; j <= Size[i]; j++) if(!vis[w[i][j]]) { ok = false; break; }
if(ok && use + t[i] <= limit && topo[i] > topo[pre])
{ canfinish = true; break; }
}
for(int i = finish; i <= n; i++) if(! vis[i])
{
bool ok = true;
for(int j = 1; j <= Size[i]; j++) if(!vis[w[i][j]]) { ok = false; break; }
if(! ok) continue;
vis[i] = true;
if(use + t[i] <= limit && topo[i] > topo[pre]) dfs(day, use + t[i], i);
else if(! canfinish) dfs(day + 1, t[i], 0);
vis[i] = false;
}
return;
}
int main(){
freopen("cost.in", "r", stdin);
freopen("cost.out", "w", stdout);
scanf("%d%d", &n, &limit);
for(int i = 1; i <= n; i++) scanf("%d", &t[i]);
while(scanf("%d%d", &x, &y) == 2) mem[x][y] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) if(i != j && mem[i][j] == 1){
in[j]++;
size[i]++; f[i][size[i]]=j;
Size[j]++; w[j][Size[j]]=i;
}
maketopo();
ans = n;
dfs(1, 0, 0);
printf("%d\n", ans);
return 0;
}
``````

2022-12-30 15:06

2022-12-08 15:09

2022-12-09 15:39

2022-12-16 20:33

2022-12-31 16:55

2022-12-05 11:18

2022-12-13 00:19

2022-12-08 16:52