首页 > 代码库 > CodeForces 789E bfs建模,思维

CodeForces 789E bfs建模,思维

2024-10-24 02:12:02   213人阅读

CodeForces 789E

题意：有k种可乐，每种的测试为ai/1000。 要你合成一种浓度为n/1000的可乐，问最小要杯可乐，每种可乐可重复取。

tags：  要注意到浓度绝不会超过1000/1000。

假设选取m杯可乐，则 (a1+a2+......+am) / m = n，变换一下为(a1-n)+(a2-n)+......+(am-n) = 0。即要选 m杯可乐，其浓度减 n之和为0。而浓度不超过1000，故(a1-n)+(a2-n)+....+(as-n)的和肯定在 -1000~1000之间，所以可以 bfs解，相当于找一条浓度0 到浓度0 的路径，边长为(ai-n)，这样到每个可能浓度点的距离一定是最近的。  还有一个坑点，a[i]数组太多，要去重。

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 1000005, M = 1010;int n, k, a[N], path[M<<1];bool vis[M<<1];int bfs(int u){    queue<int > q;    q.push(u); vis[u]=1;    int to;    while(!q.empty())    {        u=q.front(); q.pop();        rep(i,1,k)        {            to=u+a[i];            if(to==0)  return u+1000;            if(-1000<=to && to<=1000)            {                int x=to+1000;                if(vis[x]==0) {                    vis[x]=1;                    q.push(to);                    path[x]=u+1000;                }            }        }    }    return -1;}int main(){    scanf("%d %d", &n, &k);    rep(i,1,k) {        scanf("%d", &a[i]);        a[i] -= n;    }    sort(a+1, a+1+k);    int k1=unique(a+1, a+1+k)-(a+1);    k=k1;    int ans=bfs(0);    if(ans==-1) puts("-1");    else {        int cnt=1;        while(path[ans]!=0) ans=path[ans], ++cnt;        printf("%d\n", cnt);    }    return 0;}

CodeForces 789E bfs建模,思维


联系
我们