【Codeforces 1106B】Lunar New Year and Food Ordering
and Codeforces New year
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
把所有的菜按照价格升序排序. 对于每一个顾客的kind,num 先减少菜的数量。 然后定义一个变量last 表示last之前的菜都已经售空(排序后,每个人可能会有多余的部分,要用前面最小的若干部分填充) 所以每个人都会让价格低的前面的一部分菜清空。 我们每次给某个顾客填充的时候,只要从那个零界点开始填充就好 然后不要一个订单一个订单(单个)的处理 而应该一个菜一个菜的遍历 这样复杂度才是线性的。【代码】
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static class Pair implements Comparable<Pair>{
int x,id;
public Pair(int x,int id) {
this.x = x;this.id = id;
}
@Override
public int compareTo(Pair arg0) {
if (arg0.x==this.x)
return this.id-arg0.id;
else return this.x-arg0.x;
}
}
static int n,m;
static int rest[],Cost[],l[],r[];
static Pair a[];
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
n = in.nextInt();m = in.nextInt();
rest = new int[n];
a = new Pair[n];
l = new int[n+10];
r = new int[n+10];
Cost = new int[n+10];
for(int i = 0;i < n;i++) rest[i]= in.nextInt();
for (int i = 0;i < n;i++) {
a[i] = new Pair(0,i);
a[i].x = in.nextInt();
Cost[i] = a[i].x;
}
Arrays.sort(a);
int last = 0;
for (int i = 1;i <= m;i++) {
long cost = 0;
int kind,num;
kind = in.nextInt();num = in.nextInt();
kind--;
int temp = Math.min(num, rest[kind]);
rest[kind]-=temp;
num-=temp;
cost += 1l*temp*Cost[kind];
while(num>0 && last <n) {
temp = Math.min(num, rest[a[last].id]);
rest[a[last].id]-=temp;
num-=temp;
cost+=(long)1l*temp*Cost[a[last].id];
if (rest[a[last].id]==0) {
last++;
}
}
if (num!=0) cost = 0;
System.out.println(cost);
}
}
}
相关文章
- [AWS - Monitoring and Troubleshooting] 5.1 Write code that can be monitored
- [CSS] Create Complex Shapes with CSS Clip Path and Border Radiusc (border-radius & clip-path)
- [CSSinJS] Convert Sass (SCSS) Styled Button to CSSinJS with JavaScript Templates and Variables
- [Functional Programming Monad] Map And Evaluate State With A Stateful Monad
- [Angular 2] Managing State in RxJS with StartWith and Scan
- [Hapi.js] POST and PUT request payloads
- how to extend a SAPUI5 Fiori application on both view and controller in WebIDE
- 【Codeforces 385C】Bear and Prime Numbers
- 【27.40%】【codeforces 599D】Spongebob and Squares
- 【22.48%】【codeforces 689D】Friends and Subsequences
- 【47.40%】【codeforces 743B】Chloe and the sequence
- 【84.62%】【codeforces 552A】Vanya and Table
- 【codeforces 782C】Andryusha and Colored Balloons
- 【codeforces 754D】Fedor and coupons
- 【codeforces 760C】Pavel and barbecue
- 【codeforces 750F】New Year and Finding Roots
- 【codeforces 750D】New Year and Fireworks
- 【codeforces 548D】Mike and Feet
- 【codeforces 793B】Igor and his way to work
- 【codeforces 514D】R2D2 and Droid Army
- 【codeforces 508E】Artur and Brackets
- Building Microservices with Spring Boot and Apache Thrift. Part 2. Swifty services
- CodeForces 558C Amr and Chemistry (位运算,数论,规律,枚举)
- Codeforces 439D Devu and his Brother 三分
- Docker save and load镜像保存
- spinal HDL - 06 - 例化VHDL and Verilog IP