【Codeforces 1106B】Lunar New Year and Food Ordering

【链接】 我是链接,点我呀:)

【题意】

给你n个菜以及每个人需要的菜以及数量
如果某个人无法满足它对菜的需求的话
就用价格比较低的菜来填充它的要求。
(如果价格低的菜不够了,那么就直接输出0)
否则输出每个人的消费总量

【题解】

把所有的菜按照价格升序排序.
对于每一个顾客的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);

		}

	}

}