POJ3614 [USACO07NOV]防晒霜Sunscreen
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 9333 | Accepted: 3264 |
Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........
The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.
What is the maximum number of cows that can protect themselves while tanning given the available lotions?
Input
* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFi and maxSPFi
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri
Output
A single line with an integer that is the maximum number of cows that can be protected while tanning
Sample Input
3 2
3 10
2 5
1 5
6 2
4 1
Sample Output
2
Source
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm> const int INF = 0x7fffffff;
const int MAXN = + ; inline void read(int &x)
{
x = ;char ch = getchar(),c = ch;
while(ch < '' || ch > '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} int l[MAXN], r[MAXN], cnt[MAXN], point[MAXN], num[MAXN], cntt[MAXN], C, L, ans; bool cmp(int a, int b)
{
return l[a] > l[b];
} bool cmpp(int a, int b)
{
return point[a] > point[b];
} int main()
{
//freopen("data.txt", "r", stdin);
read(C),read(L);
for(register int i = ;i <= C;++ i) read(l[i]), read(r[i]), cnt[i] = i;
for(register int i = ;i <= L;++ i) read(point[i]), read(num[i]), cntt[i] = i;
std::sort(cnt + , cnt + + C, cmp);
std::sort(cntt + , cntt + + L, cmpp);
for(register int i = ;i <= C;++ i)
{
for(register int j = ;j <= L;++ j)
if(num[cntt[j]] > && r[cnt[i]] >= point[cntt[j]] && l[cnt[i]] <= point[cntt[j]])
{
--num[cntt[j]], ++ ans;
break;
}
else if(l[cnt[i]] > point[cntt[j]] ) break;
}
printf("%d", ans);
return ;
}
POJ3614
最新文章
- iOS ARC内存管理
- 响应式布局1--媒体查询和-webkit-min-device-pixel-ratio
- ios 计算缓存大小
- shell中条件判断if中的-z到-d的意思
- css+div绝对定位
- SparkSQLTest.scala
- codevs4373 窗口==poj2823 Sliding Window
- 李洪强iOS开发本人集成环信的经验总结_07_监听好友请求
- 为什么Android没有iOS那么顺滑
- php mysqli注意问题
- CodeForces 478B 第六周比赛B题
- SQL数据转移
- 《火球——UML大战需求分析》(第3章 分析业务模型-类图)——3.8 小结与练习
- 浅谈Java泛型中的extends和super关键字(转)
- 使用javassist运行时动态重新加载java类及其他替换选择
- Yii2.0源码阅读-从路由到控制器
- .NET Core WebApi中实现多态数据绑定
- Spark源码剖析 - SparkContext的初始化(三)_创建并初始化Spark UI
- 4.8 C++ typeid操作符
- 精心挑选的HTML5/CSS3应用及源码
热门文章
- iOS 更新日志 - 持续更新中
- Selenium浏览器自动化测试使用(1)
- 阿里云“网红";运维工程师白金:做一个平凡的圆梦人
- Django惰性加载和LazyObject
- 19-10-23-K-Aft
- C++标准输入问题
- 渗透神器----BurpSuite_pro_v2.1
- id 工具: 查询用户所对应的UID 和GID 及GID所对应的用户组
- linux sed命令使用疑惑总结
- 容斥原理学习(Hdu 4135,Hdu 1796)