Note
In the first example it is possible to get 8 cakes in 12 minutes using one oven. The second oven can be built in 5 minutes, so after 6minutes the first oven bakes 4 cakes, the second oven bakes 4 more ovens after 11 minutes. Thus, it is reasonable to build the second oven.
In the second example it doesn't matter whether we build the second oven or not, thus it takes 12 minutes to bake 8 cakes in both cases. Thus, it is unreasonable to build the second oven.
In the third example the first oven bakes 11 cakes in 3 minutes, that is more than needed 10. It is unreasonable to build the second oven, because its building takes more time that baking the needed number of cakes using the only oven.
现在有 n 个胡萝卜, 一个炉子, 一个炉子可以同时做 k 个胡萝卜, 做好需要 t 分钟, 现在允许用 d 分钟再造一个相同的炉子, 两个炉子可以同时工作, 判断再建一个炉子是否可以缩短总时间. 只能造一个新炉子.
开始脑子有点混, 没看明白, 其实根据样例一, 旧炉子做胡萝卜蛋糕时, 是不能做新炉子的. 首先要求出来只用旧的炉子完成任务需要的时间. 这里有个细节: 如果 n%k!=0, 那么所需炉子数 all=n/k+1. 所以此时的 alltime=all*t; 如果 d+t<alltime, 是需要建一个新炉子来缩短时间的. 因为 d 时间先做 k 个, 再造一个炉子, 这中间第一个炉子还在工作, 新炉子造完了就投入使用. 能赶在 alltime 之前造出新炉子, 那么就一定可以造出更多胡罗卜蛋糕.
代码:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- using namespace std;
- int main()
- {
- int n ,t , k ,d ;
- scanf("%d%d%d%d",&n,&t,&k,&d);
- if(k>=n)
- cout<<"NO"<<endl;
- else
- {
- int alltime ;
- if(n%k==0)
- alltime = n/k;
- else
- alltime= n/k+1;
- alltime*=t;
- if((t+d)<alltime)
- cout<<"YES"<<endl;
- else
- cout<<"NO"<<endl;
- }
- }
- B. T-shirt buying
A new pack of n t-shirts came to a shop. Each of the t-shirts is characterized by three integers pi, ai and bi, where pi is the price of the i-th t-shirt, ai is front color of the i-th t-shirt and bi is back color of the i-th t-shirt. All values pi are distinct, and values ai and bi are integers from 1 to 3.
m buyers will come to the shop. Each of them wants to buy exactly one t-shirt. For the j-th buyer we know his favorite color cj.
A buyer agrees to buy a t-shirt, if at least one side (front or back) is painted in his favorite color. Among all t-shirts that have colors acceptable to this buyer he will choose the cheapest one. If there are no such t-shirts, the buyer won't buy anything. Assume that the buyers come one by one, and each buyer is served only after the previous one is served.
- You are to compute the prices each buyer will pay for t-shirts.
- Input
- The first line contains single integer n (1≤n≤200000) - the number of t-shirts.
- The following line contains sequence of integers p1,p2,...,pn (1≤pi≤1000000000), where pi equals to the price of the i-th t-shirt.
- The following line contains sequence of integers a1,a2,...,an (1≤ai≤3), where ai equals to the front color of the i-th t-shirt.
- The following line contains sequence of integers b1,b2,...,bn (1≤bi≤3), where bi equals to the back color of the i-th t-shirt.
- The next line contains single integer m (1≤m≤200000) - the number of buyers.
The following line contains sequence c1,c2,...,cm (1≤cj≤3), where cj equals to the favorite color of the j-th buyer. The buyers will come to the shop in the order they are given in the input. Each buyer is served only after the previous one is served.
- Output
- Print to the first line m integers - the j-th integer should be equal to the price of the t-shirt which the j-th buyer will buy. If the j-th buyer won't buy anything, print -1.
- Examples
- input
- Copy
- 5
- 300 200 400 500 911
- 1 2 1 2 3
- 2 1 3 2 1
- 6
- 2 3 1 2 1 1
- output
- Copy
- 200 400 300 500 911 -1
- input
- Copy
- 2
- 1000000000 1
- 1 1
- 1 2
- 2
- 2 1
- output
- Copy
- 1 1000000000
题意是很好理解的: 有 n 件 T 恤, 每件 T 体恤都分别有价格 (价格各不相同, 这点很重要! 等一下会说明), 前面的颜色 (1,2,3), 背部的颜色三种属性. 接下来有 m 个人每个人都有一种喜欢的颜色, 他们按先后顺序选择衣服,
如果没有喜欢的颜色的衣服了就输出 "-1", 否则选择其中符合条件的衣服中价值最小的. 输出每个人要付出的钱.
看数据, 直接暴力的话会 T 的. 我们知道各体恤价格不同, 所以可以 set[] 来做, set 里的元素自动排序, 而且无重复. 比如 set[1]=100,200, 表示 1 颜色的价格有 100,200 两件. 某件衣服被买走以后, 就把所有
价格等此的数据删除, 其实因为价格各不相同, 所以我们删除的只是同一件衣服正反面颜色对应的价格而已, 就当于这件衣服删除了. 比如 set[1]=100,set[2]=100, 此处的 1,2 分别表示同一件衣服的正反面, 删除两个 100, 这件衣服就相当于没了.
具体看代码, 注意怎么得到 set[].begin(), 第一次学到.
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<set>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5+12;
- struct node
- {
- ll p,a,b;
- }st[maxn];
- int main()
- {
- int n ;
- set<ll>ss[4];
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%lld",&st[i].p);
- for(int i = 1 ; i <= n; i++)
- scanf("%lld",&st[i].a);
- for(int i = 1 ; i <= n ; i ++)
- scanf("%lld",&st[i].b);
- for(int i = 1 ; i <= n ; i++)
- {
- ss[st[i].a].insert(st[i].p); //set 用法注意
- ss[st[i].b].insert(st[i].p);
- }
- int m;
- scanf("%d",&m);
- for(int i =1 ; i <= m ; i ++)
- {
- int x ;
- scanf("%d",&x);
- if(ss[x].size()==0) //set 用法注意
- cout<<"-1";
- else
- {
- ll mid = *(ss[x].begin()); //set 用法注意
- cout<<mid<<" "; // 此时的. begin() 为当前颜色里价格最便宜的衣服
- for(int i= 1;i<=3;i++)
- {
- ss[i].erase(mid);
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3374863.html