[USACO1.3] 混合牛奶 Mixing Milk

题目描述

由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。

Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格可能相同。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。

给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

注：每天所有奶农的总产量大于 Marry 乳业的需求量。

输入格式

第一行二个整数 $n,m$，表示需要牛奶的总量，和提供牛奶的农民个数。

接下来 $m$ 行，每行两个整数 $p_i,a_i$，表示第 $i$ 个农民牛奶的单价，和农民 $i$ 一天最多能卖出的牛奶量。

输出格式

单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 $100\%$ 的数据：
$0 \le n,a_i \le 2 \times 10^6$，$0\le m \le 5000$，$0 \le p_i \le 1000$

题目翻译来自 NOCOW。

USACO Training Section 1.3

题解

思路

每次取最优的结果，例如找最小值时就每个数组都找最小的，然后这里的陷阱时不用每次都取完总量，要比较总量和需求的大小，哪个小去哪个。

代码

#include<bits/stdc++.h>
using namespace std;

struct peo {
    int p, a;
};

peo milk[1001];

bool cmp(peo x, peo y) {
    return x.p<y.p;
}

int main() {
    int n, m, sum = 0; 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> milk[i].p >> milk[i].a;
    }
    sort(milk, milk + m, cmp); 
    for(int i=0;i<m&&n>0;i++){
    	int buy=min(n,milk[i].a);
    	sum+=buy*milk[i].p;
    	n-=buy;
	}
    cout << sum << endl;
    return 0;
}

跳跳！

题目描述

你是一只小跳蛙，你特别擅长在各种地方跳来跳去。

这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头，其中第 $i$ 块的石头高度为 $h_i$，地面的高度是 $h_0 = 0$。你估计着，从第 $i$ 块石头跳到第 $j$ 块石头上耗费的体力值为 $(h_i - h_j) ^ 2$，从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i) ^ 2$。

为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次，并最终停在任意一块石头上，并且小跳蛙想耗费尽可能多的体力值。

当然，你只是一只小跳蛙，你只会跳，不知道怎么跳才能让本领更充分地展现。

不过你有救啦！小 F 给你递来了一个写着 AK 的电脑，你可以使用计算机程序帮你解决这个问题，万能的计算机会告诉你怎么跳。

那就请你——会写代码的小跳蛙——写下这个程序，为你 NOIp AK 踏出坚实的一步吧！

输入格式

输入一行一个正整数 $n$，表示石头个数。

输入第二行 $n$ 个正整数，表示第 $i$ 块石头的高度 $h_i$。

输出格式

输出一行一个正整数，表示你可以耗费的体力值的最大值。

样例 #1

样例输入 #1

1
2

2
2 1

样例输出 #1

样例 #2

样例输入 #2

1
2

3
6 3 5

样例输出 #2

提示

样例解释

两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。

数据范围

对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。

对于 $10\%$ 的数据，$n \leq 3$；

对于 $20\%$ 的数据，$n \leq 10$；

对于 $50\%$ 的数据，$n \leq 20$；

对于 $80\%$ 的数据，$n \leq 50$；

对于 $100\%$ 的数据，$n \leq 300$。

题解

思路

贪心的思想，每次取得最优解，方法一是用两个变量，一个取最大另一个取最小，交替取，然后再求代价（求最大和最小差的平方）。方法二则是计算代价的方法不一样。

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,k=0;
	cin>>n;
	int h[10001],m[10001];
	long long value = 0;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	sort(h,h+n);
	m[0]=0;
	for(int i=0;i<n;i++){
		m[i+1]=h[i];
	}
	
	int l = 0,r = n;
	while(true){
		if(l==r){
			break;
		}
		if(k%2==0){
			value +=(m[r]-m[l])*(m[r]-m[l]);
			k++;
			l++;
		}
		else{
			value +=(m[r]-m[l])*(m[r]-m[l]);
			k++;
			r--;
		}
				
	}
		
	cout<<value<<endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
unsigned long long ans=0;
int h[330];
bool sum=0;
signed main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>h[i];
	}
	sort(h+1,h+n+1);
	int j=0,hpast=0;
	for (int i=1;i<=n;i++)
	{
		j=n-j+sum;
		sum=!sum;
		ans+=(h[j]-hpast)*(h[j]-hpast);
		hpast=h[j];
	}
	cout<<ans;
	return 0;
}

[NOIP2007 普及组] 纪念品分组

题目背景

NOIP2007 普及组 T2

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

共 $n+2$ 行：

第一行包括一个整数 $w$，为每组纪念品价格之和的上限。

第二行为一个整数 $n$，表示购来的纪念品的总件数 $G$。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

一个整数，即最少的分组数目。

样例 #1

样例输入 #1

样例输出 #1

提示

$50\%$ 的数据满足：$1\le n\le15$。

$100\%$ 的数据满足：$1\le n\le3\times10^4$，$80\le w\le200$，$5 \le P_i \le w$。

题解

思路

贪心的过程就是先将数组按照升序排序，然后用两个变量去分别取最大和最小，让两个相加然后判断是否比需求小，小就都移动变量，如果不小，就移动一个变量再判断。

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
	int w,k;
	cin>>w;
	long long n;
	cin>>n;
	int p[1001];
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	sort(p,p+n);
	int a,b;
	a=0;b=n-1;
	while(a<=b){
		if(p[a]+p[b]<=w){
			a++;
			b--;
			k++;
		}
		else{
			b--;
			k++; 
		}
			
	}
	
	cout<<k<<endl;
	return 0; 
}

[NOIP2010 普及组] 三国游戏

题目描述

小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。

在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有 $N$ 位武将（$N$ 为偶数且不小于 $4$），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。

游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵 $\to$ 计算机 $\to$ 小涵 $\to\dots$ ”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。

已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。下面举例说明计算机的选将策略，例如，游戏中一共有$6$个武将，他们相互之间的默契值如下表所示：

武将编号	1	2	3	4	5	6
1		$5$	$28$	$16$	$29$	$27$
2	$5$		$23$	$3$	$20$	$1$
3	$28$	$23$		$8$	$32$	$26$
4	$16$	$3$	$8$		$33$	$11$
5	$29$	$20$	$32$	$33$		$12$
6	$27$	$1$	$26$	$11$	$12$

双方选将过程如下所示：

	小涵	轮到计算机时可选的自由武将	计算机	计算机选将说明
第一轮	$5$	$1,2,3,4,6$	$\color{magenta}4$	小涵手中的 $5$ 号武将与 $4$ 号的默契值最高，所以计算机选择 $4$ 号。
第二轮	$5,3$	$1,2,6$	$4,\color{magenta}1$	小涵手中的 $5$ 号和 $3$ 号武将与自由武将中配对可产生的最大默契值为 $29$，是由 $5$ 号与 $1$ 号配对产生的，所以计算机选择 $1$ 号。
第三轮	$5,3,6$	$2$	$4,1,\color{magenta}2$

小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？

假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。

输入格式

共 $N$ 行。

第一行为一个偶数 $N$，表示武将的个数。

第 $2$ 行到第 $N$ 行里，第 $i+1$ 行有 $N-i$ 个非负整数，每两个数之间用一个空格隔开，表示 $i$ 号武将和 $i+1,i+2,\dots,N $ 号武将之间的默契值（$0≤\text{默契值}\le10^9$）。

输出格式

共一或二行。

若对于给定的游戏输入，存在可以让小涵获胜的选将顺序，则输出 $ 1$，并另起一行输出所有获胜的情况中，小涵最终选出的武将组合的最大默契值。如果不存在可以让小涵获胜的选将顺序，则输出 $0$。

样例 #1

样例输入 #1

6 
5 28 16 29 27 
23 3 20 1 
8 32 26 
33 11 
12

样例输出 #1

1
2

1
32

样例 #2

样例输入 #2

8 
42 24 10 29 27 12 58 
31 8 16 26 80 6 
25 3 36 11 5 
33 20 17 13 
15 77 9 
4 50 
19

样例输出 #2

1
2

1
77

提示

数据范围

对于 $ 40\%$ 的数据有 $N≤10$。

对于 $ 70\%$ 的数据有 $ N≤18$。

对于 $100\%$ 的数据有 $4\le N≤500$。保证对于不同的武将组合，其默契值均不相同。

NOIP2010 普及组第四题