|
此博客适合新手，有翻译，非常入门，为康复题集
由于是5个月前的代码，可能不是最优解，但必定正确
目录
CodeForces 893D题目描述
输入格式
输出格式?
题目翻译
输入输出样例
AtCoder - abc085_d题目描述
输入格式
输出格式
题意翻译
输入输出样例
CodeForces 42A题目描述
输入格式
输出格式?
题目翻译
输入输出样例
POJ-2431题目描述
输入格式
输出格式?
题目翻译
输入输出样例
CodeForces 893D题目描述
- Recenlty Luba got a credit card and started to use it. Let's consider n?consecutive days Luba uses the card.
- She starts with 0?money on her account.
- In the evening of i?-th day a transaction ai occurs. If a_{i}>0 , then ai bourles are deposited to Luba's account. If a_{i}<0 , then ai bourles are withdrawn. And if ai=0 , then the amount of money on Luba's account is checked.
- In the morning of any of nn days Luba can go to the bank and deposit any positive integer amount of burles to her account. But there is a limitation: the amount of money on the account can never exceed dd .
- It can happen that the amount of money goes greater than dd by some transaction in the evening. In this case answer will be ?-1?.
- Luba must not exceed this limit, and also she wants that every day her account is checked (the days when ai=0 ) the amount of money on her account is non-negative. It takes a lot of time to go to the bank, so Luba wants to know the minimum number of days she needs to deposit some money to her account (if it is possible to meet all the requirements). Help her!
输入格式
- The first line contains two integers n?, d( 1<=n<=10^{5}, 1<=d<=10^{9}) —the number of days and the money limitation.
- The second line contains n?integer numbers a1,a2,... an ( -10^{4}<=ai<=10^{4}), where ai represents the transaction in i?-th day.
输出格式?
- Print -1 if Luba cannot deposit the money to her account in such a way that the requirements are met. Otherwise print the minimum number of days Luba has to deposit money.
题目翻译
Recenlty Luba有一张信用卡可用，一开始金额为0，每天早上可以去充任意数量的钱
到了晚上，银行会对信用卡进行一次操作，操作有三种操作
1.如果a[i]>0，银行会给卡充入a[i]元
2.如果a[i]<0 银行从卡中扣除a[i]元
3.如果a[i]=0 银行会查询卡里的金额
有两条规则，如果违背信用卡就会被冻结
?1.信用卡里的金额不能大于d
2.当银行查询卡里的金额时，金额不能为负
Recenlty Luba想知道最少去充多少次钱，可以使她在接下来的n天里信用卡不被冻结
输入输出样例
输入 #1
5 10
-1 5 0 -5 3
输出 #1
0
输入 #2
3 4
-10 0 20
输出 #2
-1
输入 #3
5 10
-5 0 10 -11 0
输出 #3
2
#include<bits/stdc++.h>
using namespace std;
int n,d,a[199999];
int s1=0,s2=0,k=0;
int main(){
cin>>n>>d;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
if(!a[i]){
if(s1<0){
s1=0;
}
if(s2<0){
s2=d;
k++;
}
}
else{
s1+=a[i];
s2+=a[i];
if(s1>d){
puts("-1");
return 0;
}
if(s2>d){
s2=d;
}
}
}
cout<<k<<endl;
return 0;
}
AtCoder - abc085_d题目描述
- You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have N?katana (swords), Katana 1, Katana 2, ……, Katana N, and can perform the following two kinds of attacks in any order:
- Wield one of the katana you have. When you wield Katana ii (1 ≤ i ≤ N), the monster receives a_iai points of damage. The same katana can be wielded any number of times.
- Throw one of the katana you have. When you throw Katana ii (1 ≤ i ≤ N)?at the monster, it receives b_ibi points of damage, and you lose the katana. That is, you can no longer wield or throw that katana.
- The monster will vanish when the total damage it has received is H?points or more. At least how many attacks do you need in order to vanish it in total?
输入格式
N H
a1? b1?
:
aN? bN?
- 1≤N≤105
- 1 ≤ H ≤ 10^9
- 1≤ai≤bi≤109
- All input values are integers.
输出格式
Print the minimum total number of attacks required to vanish the monster.
题意翻译
有N把武士刀，对于每一把武士刀，有以下两种攻击方法：
①常规：攻击造成a点damage，可连续多次使用；
②终结：攻击造成b点damage，使用一次后丢弃。
对于每一把武士刀，有a≤b。
为造成至少H点的damage，求最小攻击次数
输入输出样例
输入 #1
4 1000000000
1 1
1 10000000
1 30000000
1 99999999
输出 #1
860000004
输入 #2
5 500
35 44
28 83
46 62
31 79
40 43
输出 #2
9
#include<bits/stdc++.h>
using namespace std;
long long n,i,h,k,ss=0,v=1;
struct stu{
long long a,b;
}s[100050];
bool cmp(stu x,stu y){
return x.a>y.a;
}
bool cmp1(stu x,stu y){
return x.b>y.b;
}
int main()
{
cin>>n>>h;
for(i=1;i<=n;i++){
scanf("%lld %lld",&s[i].a,&s[i].b);
}
sort(s+1,s+1+n,cmp);
k=s[1].a;
sort(s+1,s+1+n,cmp1);
i=1;
if(v==1){
for(;i<=n;i++){
if(s[i].b>=k){
h-=s[i].b;
ss++;
}
if(h<=0){
cout<<ss;
return 0;
}
else if(s[i].b<k){
v=2;
break;
}
}
if(i==n+1){
v=2;
}}
if(v==2){
if(h%k==0){
ss+=(h/k);}
else{
ss+=(h/k);
ss++;
}
cout<<ss;
return 0;
}
return 0;
}
CodeForces 42A题目描述
- It's a very unfortunate day for Volodya today. He got bad mark in algebra and was therefore forced to do some work in the kitchen, namely to cook borscht (traditional Russian soup). This should also improve his algebra skills.
- According to the borscht recipe it consists of n ingredients that have to be mixed in proportion a1:a2...an
- litres (thus, there should be a1?x,...,an?x litres of corresponding ingredients mixed for some non-negative x ). In the kitchen Volodya found out that he has b1,...,bn litres of these ingredients at his disposal correspondingly. In order to correct his algebra mistakes he ought to cook as much soup as possible in a V litres volume pan (which means the amount of soup cooked can be between 0 and V litres). What is the volume of borscht Volodya will cook ultimately?
输入格式
- The first line of the input contains two space-separated integers n and V (1<=n<=20,1<=V<=10000 ).
- The next line contains n space-separated integers ai ( 1<=ai<=100 ). Finally, the last line contains n space-separated integers bi ( 0<=bi<=100 ).
输出格式?
- Your program should output just one real number — the volume of soup that Volodya will cook.
- Your answer must have a relative or absolute error less than 10^{-4} .
题目翻译
今天对Volodya来说是十分不幸的一天。他的代数考试挂掉了，并且不得不在厨房里干活，即做罗宋汤（一种传统的俄罗斯汤）。通过这样也能提高他的代数水平。
根据罗宋汤的配方,罗宋汤由nn部分组成，并且它们必须按比例（a1?:a2?:…:an?）混合（因此，对于一个非负的x，它们为a1??x,a2??x,…,an??x升），在厨房里 Volodya发现每种配料他相应的有b1?,b2?,…,bn?升供他使用
为了纠正他在代数上的错误，他决定用一个容量为V升的锅尽可能的多做汤（这意味着这它能够做0到V升的汤）
Volodya最多能做多少汤？
输入输出样例
输入 #1
1 100
1
40
输出 #1
40.0
输入 #2
2 100
1 1
60 60
输出 #2
100.0
#include<bits/stdc++.h>
using namespace std;
int i,n;
double a[10050],b[10050],k=9999,s=0,v;
int main(){
cin>>n>>v;
for(i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
for(i=1;i<=n;i++){
scanf("%lf",&b[i]);
k=min(k,b[i]/a[i]);
}
for(i=1;i<=n;i++){
s+=k*a[i];
if(s>=v){
printf("%.4lf",v);
return 0;
}
}
printf("%.4lf",s);
return 0;
}
POJ-2431题目描述
- A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck now leaks one unit of fuel every unit of distance it travels.
- To repair the truck, the cows need to drive to the nearest town (no more than 1,000,000 units distant) down a long, winding road. On this road, between the town and the current location of the truck, there are N (1 <= N <= 10,000) fuel stops where the cows can stop to acquire additional fuel (1..100 units at each stop).
- The jungle is a dangerous place for humans and is especially dangerous for cows. Therefore, the cows want to make the minimum possible number of stops for fuel on the way to the town. Fortunately, the capacity of the fuel tank on their truck is so large that there is effectively no limit to the amount of fuel it can hold. The truck is currently L units away from the town and has P units of fuel (1 <= P <= 1,000,000).
- Determine the minimum number of stops needed to reach the town, or if the cows cannot reach the town at all.
输入格式
- * Line 1: A single integer, N
- * Lines 2..N+1: Each line contains two space-separated integers describing a fuel stop: The first integer is the distance from the town to the stop; the second is the amount of fuel available at that stop.
- * Line N+2: Two space-separated integers, L and P
输出格式?
- * Line 1: A single integer giving the minimum number of fuel stops necessary to reach the town.
- If it is not possible to reach the town, output -1.
题目翻译
Xavier养的一群奶牛劫持了一个卡车，并向丛林中逃亡
由于奶牛们不会开车，卡车不幸地撞上了丛林中的一块岩石，并撞破了油箱
于是他们每行驶一个单位距离，油箱就漏一单位油
?为了修理这个卡车，奶牛们需要沿着一条长长的公路行驶到最近的一个城镇
在这条路上，在卡车当前位置和城镇之间，有N个加油站，每个加油站有不多于100单位的汽油
?丛林对于人类来说是个危险的地方，更不用说奶牛了
因此，奶牛们想要他们停下加油的次数尽量少
幸运的是，卡车的油箱是如此的大，可以容纳任意多的汽油
卡车现在距离城镇L单位长度，油箱里有P单位的油
?请求出奶牛们最少的加油次数，或者他们根本无法到达城镇，无解请输出-1
第一行有一个整数N(N <= 10 , 000)
下面N行，每行两个整数，分别代表每个加油站与城镇的距离和本加油站拥有的汽油量
最后一行有两个整数，L和P。(1 <= P <= 1 , 000 , 000) 如果奶牛们能到达城镇，输出一个整数，代表最少加油的次数。否则输出-1
输入输出样例
输入 #1
4
4 4
5 2
11 5
15 10
25 10
输出 #1
2
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,k,l,p,kk,sss=0,xx,yy;
struct stu{
int a;
int b;
}s[1000050];
priority_queue<int> ss;
bool cmp(stu x,stu y){
return x.a<y.a;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d %d",&s[i].a,&s[i].b);
}
scanf("%d %d",&l,&p);
yy=p;
s[n+1].b=0;
s[n+1].a=l;
for(i=1;i<=n;i++){
s[i].a=l-s[i].a;
}
sort(s+1,s+n+2,cmp);
for(i=1;i<=n+1;i++){
kk=s[i].a-xx;
while(yy<kk){
if(ss.empty()){
k=1;
break;
}
yy+=ss.top();
ss.pop();
sss++;
}
yy-=kk;
xx=s[i].a;
ss.push(s[i].b);
if(k==1){
break;
}
}
if(k==1){
cout<<-1<<endl;
}
else{
printf("%d\n",sss);
}
return 0;}
|