2020-08-09
http://icpc.upc.edu.cn/problem.php?id=14866
题目¶
14866: 高兴天数
题目描述¶
小X性格很独特，如果她今天高兴度比上次一样或更高，她就会很善良，相反，如果她今天高兴度比上次低，她就会很凶！现在已经知道小X在N天里每天的高兴度M。根据这N天中她每天高兴度M，合理安排与她相处时间，使大家与小X友好相处尽量多天数。现在要求计算出最多能和小X友好相处多少天。
输入¶
共2行，第一行为一个N，第二行为N个数，为小X每天的高兴程度M。
输出¶
共1个数，最多能和小X友好相处多少天。
样例输入¶
样例输出¶
提示¶
对于30%的数据，N<=8000 对于100%的数据，N，M<31000
解析¶
二分法求最大上升子序列 这里解释一下：题目所说的“比上次”是指我们和她相处的上一次，而不是指前一天。例如，第三天和她相处后隔了两天后即第六天又与她相处，应该拿第六天心情和第三天心情比较。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[300500]={0};
ll c[300500]={0};
int main()
{
ll n,cnt=0;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",a+i);
for(ll i=1;i<=n;i++)
{
if(a[i]>=c[cnt])
{
c[++cnt]=a[i];
}
else
{
ll l=1,r=cnt+1;
while(l<r)
{
ll mid=(l+r)/2;
if(a[i]>c[mid])
{
l=mid+1;
}
else if(a[i]<c[mid])
{
r=mid;
}
else if(a[i]==c[mid])
{
l=mid+1;
}
}
c[l]=min(c[l],a[i]);
}
}
printf("%lld\n",cnt);
return 0;
}
题目¶
15036: 选择
题目描述¶
哈哈哈，快忘掉你的烦心事，找张位子坐下来。 beny和fife两人作为彼此炉边好友，决定来一场惊心动魄的友谊（py）赛。 fife有n个随从，第i个随从有一个能力值，为A[i]。 beny也有对应的n个随从，第i个随从同样也有一个能力值，为B[i]。 然后，一群随从的战斗力为这群随从能力值的总和。 现在，beny和fife每个人都派出自己第L个到第R个（共R-L+1个随从），来一决高下。 但是由于他们在一绝高下的同时要py任务，他们要你选择一对(L,R)，使双方战斗力差距最小。 他们要你输出最小的战斗力差距（战斗力较大的减战斗力较小的）。
输入¶
第一行一个正整数n。 第二行n个整数，表示数组A。 第三行n个整数，表示数组B。
输出¶
一行一个正整数， 表示最小的战斗力差距。
样例输入¶
【样例1】 3 4 2 3 3 4 2 【样例2】 5 38 19 5 17 3 15 22 0 6 17
样例输出¶
【样例1】 0 【样例2】 1
提示¶
样例1解释：L = 1， R = 3
样例2解释：L = 2， R = 5
set的应用
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[300500]={0};
ll b[300500]={0};
ll c[300500]={0};
set<ll>::iterator it1,it2;
ll x,y,n,ans=99999999999;
set<ll>w;
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&b[i]);
c[i]=c[i-1]+b[i]-a[i];
}
w.insert(0);
w.insert(99999999999);
for(ll i=1;i<=n;i++)
{
it1=w.upper_bound(c[i]);
it2=it1;
it2--;
x=*it1;
y=*it2;
ans=min(ans,abs(c[i]-x));
ans=min(ans,abs(c[i]-y));
w.insert(c[i]);
}
printf("%lld\n",ans);
}