洛谷 题解 P4613 【[COCI2017-2018#5] Olivander】
2024-09-01 12:26:23
我又双叒叕被包菜辣!
P4613 [COCI2017-2018#5] Olivander
首先,不知道为什么这题无法提交翻译;
所以,我先放个翻译:
哈利波特在与伏地魔的战斗中损坏了他的魔杖。他决定在奥利凡德的魔杖店买一根新的
魔杖。在商店的地板上,他看到了n根魔杖和n个魔杖盒。魔杖的长度分别是,x1,x2,
…,xn,盒子的尺寸是y1,y2,….y.如果x≤y,可以将x长度的魔杖放在y尺寸的盒子中。
哈利想知道他是否能把所有的魔杖都放在盒子里,这样每个盒子里只有一根魔杖。
帮助他解决这个难题。如果可以放入即输出“DA”,否则输出“NE”;
我先讲一下这道题的正解,先把魔杖的长度和盒子的长度按从大到小排序,然后依次对比每个魔杖的长度和盒子的长度,如果Rep(1, n)中存在x[i] > y[i]那么就无法成功装入。先上代码,讲解在后面(如果只是为了抄代码的就不用往后翻了:
#include<bits/stdc++.h>
using namespace std;
#define maxn 110//数据很小,空间很大,你想开多大就多大(划掉
int n, x[maxn], y[maxn];//x[i]和y[i]都如题,分别是魔杖的长度和盒子的长度
bool cmp(int a, int b)//排序用的cmp,从大到小。
{
return a > b;
}
int main()
{
scanf("%d", &n);//个数
for(int i = 1; i <= n; ++ i)
scanf("%d", &x[i]);//魔杖的长度
for(int i = 1; i <= n; ++ i)
scanf("%d", &y[i]);//盒子的长度
sort(x + 1, x + n + 1, cmp);//从大到小排序,其实也可以从小到大,在后面逆序一下就行了,只有保证有序即可
sort(y + 1, y + n + 1, cmp);//同上
for(int i = 1; i <= n; ++ i)
if(y[i] < x[i])//存在魔杖的长度比盒子的长度要大
{
printf("NE");//输出
return 0;
}
printf("DA");//输出
return 0;
}
然后,开始分析这道题(好水:
我们试想一下,如果存在x[k]比y[k]要大,那么我没会发生什么?
设k前面有只有一个数
x[] : 10 8
y[] : 11 7
很明显在k这一组,y[k]不可能装下x[k],
又因为我们已经排好序了,所以在y[k]后面的一点不可能比y[k]大。
那么只可能是y[k],比如说y[m],前面的来装x[k],如果前面的来装x[k]了;
那么y[m]怎么办?x[k]肯定装不了,继续往前?那第一个怎么办?
所以,证毕。
PS:请看懂再抄
最新文章
- MVC, MVP, MVVM比较以及区别
- win7桌面背景地址
- xib命名注意事项--防止被其他控制器意外地 当做默认的 view了
- redis的单实例配置+web链接redis
- Overcome the Dilemma of ";unlock"; and ";trust";
- BaseAdapter&;ArrayAdapter在ListView中应用
- 使用Python,字标注及最大熵法进行中文分词
- Linux系列教程(二十)——Linux的shell概述以及如何执行脚本
- 【阿里聚安全&#183;安全周刊】双十一背后的“霸下-七层流量清洗”系统| 大疆 VS “白帽子”,到底谁威胁了谁?
- php redis 操作
- dpr,ppi,dip,viewport的一些概念
- pstack跟踪进程栈
- JAVA中的责任链模式(CH02)
- mysql data type <;---->; java data type (数值)
- 【python学习-4】可复用函数与模块
- Python学习笔记(六)—— 条件判断
- 【Delphi】SPComm注意事项
- each与list的用法(PHP学习)
- IOS6新特性之下拉刷新<;UIRefreshControl>;
- [ACM_数据结构] HDU 1166 敌兵布阵 线段树 或 树状数组