long otto 需要 mem 比较 scanf microsoft esp
首先将蚂蚁按照血量从大到小排序,并把鞋子(可以使用结构体或
来保存鞋子的伤害值和费用)按照伤害值从高到低排序。
- pair
逐个计算每只蚂蚁需要用哪双鞋子来踩,对于当前蚂蚁的血量 ant,把所有伤害值不小于 ant 的鞋子放入优先队列中。
在这个优先队列中,费用低的鞋子优先级越高。
在每次将鞋子放入优先队列后,让优先队列的队首元素(费用最低的鞋子)出队并累积总费用。
不断循环,直到算出每只蚂蚁对应的鞋子,或者发现没有可用的鞋子时直接输出
。
- No
看了提示之后还是写了半天,基础太烂了。。渣渣来讲一下做这题的过程。
贪心策略不多说,挺好理解的。就是对重载不太知道怎么写。用个结构体定义鞋子。
然后重载运算符,这样才可以使用元素类型为 shoe 的优先队列。
- struct shoe
- {
- int price;
- int power;
- //定义在优先队列中的优先级 价格低的优先级高
- bool operator< (constshoe & a)const
- {
- returnprice > a.price;
- }
- } shoes[100005];
在网上看到另外一个方法,感觉挺有用,但是代码比较长,就换成了上面的。同时使用下面的方法定义优先级时
声明优先队列的方式要变化 priority_queue<shoe,vector<shoe>,Cmp> q;
- //定义在优先队列中的优先级的另一种方式 价格低的优先级高
- //priority_queue<shoe,vector<shoe>,Cmp> q;
- struct Cmp
- {
- bool operator() (shoe s1, shoe s2)
- {
- if(s1.price==s2.price)returns1.power>s2.power;
- returns1.price > s2.price;
- }
- };
然后就开始暴露我的智商了。先贴一波第五组数据超时的代码
- #include
- #include
- #include <set>
- #include
- #include
- #include <string>
- #include
- #include using namespace std;
- int n,m;
- intants[100005];
- intvis[100005];
- struct shoe
- {
- int index;
- int price;
- int power;
- //定义在优先队列中的优先级 价格低的优先级高
- bool operator< (constshoe & a)const
- {
- returnprice > a.price;
- }
- } shoes[100005];
- //定义在优先队列中的优先级的另一种方式 价格低的优先级高
- //priority_queue<shoe,vector<shoe>,Cmp> q;
- struct Cmp
- {
- bool operator() (shoe s1, shoe s2)
- {
- if(s1.price==s2.price)returns1.power>s2.power;
- returns1.price > s2.price;
- }
- };
- boolcmp(intx,int y)
- {
- returnx>y;
- }
- boolcmpshoes(shoe &s1,shoe &s2)
- {
- returns1.power>s2.power;
- }
- int main ()
- {
- memset(vis,0,sizeof(vis));
- scanf("%d%d",&n,&m);
- for(inti=0; i)
- scanf("%d",&ants[i]);
- for(inti=0; i)
- {
- scanf("%d",&shoes[i].power);
- shoes[i].index=i;
- }
- for(inti=0; i)
- scanf("%d",&shoes[i].price);
- sort(ants,ants+n,cmp);
- sort(shoes,shoes+m,cmpshoes);
- long longans=0;
- intflag=1;
- for(inti=0; i)
- {
- //priority_queue<shoe,vector<shoe>,Cmp> q;priority_queue q;
- intj=0;
- while(j=ants[i])
- {
- if(!vis[shoes[j].index])
- q.push(shoes[j]);
- j++;
- }
- //while(vis[q.top().index]&&!q.empty()) q.pop();
- if(q.empty())
- {
- flag=0;
- break;
- }
- //cout<<"top:"<<q.top().index<<" "<<q.top().power<<" "<<q.top().price<<endl;ans+=q.top().price;
- vis[q.top().index]=1;
- }
- if(flag) printf("%lld\n",ans);
- elseprintf("No\n");
- return 0;
- }
在此之前第四组数据都超时。。因为我把每双鞋子都往里塞,再把用过的慢慢弹...
然后想了半天要怎么优化才能过最后一组数据。然后突然想到
优先队列应该开在外部,不应该开在内部,因为蚂蚁的血量是从大到小排序的,下一只蚂蚁的血量一定能用能踩死当前蚂蚁的鞋子踩死,只要加入新的能踩死的鞋子就好。
然后用掉的鞋子弹出队列,也不需要 vis 数组来标记了。好吧 我是 zz。。
- #include
- #include
- #include <set>
- #include
- #include
- #include <string>
- #include
- #include using namespace std;
- int n,m;
- intants[100005];
- intvis[100005];
- struct shoe
- {
- int price;
- int power;
- //定义在优先队列中的优先级 价格低的优先级高
- bool operator< (constshoe & a)const
- {
- returnprice > a.price;
- }
- } shoes[100005];
- //定义在优先队列中的优先级的另一种方式 价格低的优先级高
- //priority_queue<shoe,vector<shoe>,Cmp> q;
- struct Cmp
- {
- bool operator() (shoe s1, shoe s2)
- {
- if(s1.price==s2.price)returns1.power>s2.power;
- returns1.price > s2.price;
- }
- };
- boolcmp(intx,int y)
- {
- returnx>y;
- }
- boolcmpshoes(shoe &s1,shoe &s2)
- {
- returns1.power>s2.power;
- }
- int main ()
- {
- memset(vis,0,sizeof(vis));
- scanf("%d%d",&n,&m);
- for(inti=0; i)
- scanf("%d",&ants[i]);
- for(inti=0; i)
- {
- scanf("%d",&shoes[i].power);
- }
- for(inti=0; i)
- scanf("%d",&shoes[i].price);
- sort(ants,ants+n,cmp);
- sort(shoes,shoes+m,cmpshoes);
- long longans=0;
- intflag=1;
- //优先队列开在外部 不应该开在内部 因为蚂蚁的血量是从大到小排序的
- //下一只蚂蚁的血量一定能用能踩死当前蚂蚁的鞋子踩死
- //priority_queue<shoe,vector<shoe>,Cmp> q;priority_queue q;
- intj=0;
- for(inti=0; i)
- {
- while(j=ants[i])
- {
- q.push(shoes[j]);
- j++;
- }
- if(q.empty())
- {
- flag=0;
- break;
- }
- ans+=q.top().price;
- q.pop();
- }
- if(flag) printf("%lld\n",ans);
- elseprintf("No\n");
- return 0;
- }
计蒜客——踩蚂蚁
来源: http://www.bubuko.com/infodetail-2030159.html