sern
Description
ERROR! Human is dead. Mismatch.
SERN妄图研发出时间机器，然而现在却只有一堆失败的实验品。
然而，SERN妄图通过这些失败的试验品研究出正确的道路，而这首先就需要将这些失败的实验品归类。
每一个实验品有一个转移强度D和转移距离R。由于SERN血腥残忍、不择手段，所以所有实验品的转移强度均不相同，转移距离也均不相同。
SERN惊讶的发现，一个时间机器的性能极大地取决于它在高斯平面上的投影。
定义一个时间机器α在高斯平面上的投影λ(α)“傅里叶包含”【“傅里叶包含"记作”)("】另一个时间机器β在高斯平面上的投影λ(β)【此关系记作"α)(β"】，当且仅当α的转移强度大于β的转移强度且α的转移距离大于β的转移距离。
定义黎曼-洛伦兹函数ζ(A,S)为真当且仅当在实验品集合S中的任何实验品在高斯平面上的投影都不傅里叶包含实验品A在高斯平面上的投影，亦即对于任意B∈S，"B)(A"不成立。
而对实验品的归类方式可以分为以下几个步骤：
S1：令i=0
S2：令i=i+1 令S=还没被分组的实验品集合
S3：对于每一件S中的武器A，如果黎曼-洛伦兹函数ζ(A,S)为真，则将武器A标记为第i组
【注意S在这个过程中始终保持不变，这称为分组的牛顿-科特斯一致性】
S4：如果所有实验品均被分组则结束，否则转S2
给定N个实验品的D和R，你的任务是将其分组。
Input
输入文件的第一行包含一个正整数N，表示实验品的个数。
接下来N行，每行两个正整数D,R，描述一个实验品的D和R.
Output
输出文件包含N行，每行一个正整数，第i行的数表示第i个实验品被分在了哪一组
Sample Input
5
1 4
2 2
3 3
4 1
5 5
Sample Output
2
3
2
2
1
对于20%的数据，N<=100
对于40%的数据，N<=3000
对于100%的数据，N<=100000，1<=R,D<=10^9
解析：排序，二分查找答案，加一个简单的DP
#include <bits/stdc++.h>
using namespace std;
int f[100001],maxr[100001];
struct A
{
int a,b,c;
}a[100001];
bool cmp (A a,A b)
{
return a.a>b.a;
}
int main()
{
int n;
scanf ("%d",&n);
for (int i=1;i<=n;i++)
{
scanf ("%d%d",&a[i].a,&a[i].b);
a[i].c=i;
}
sort (a+1,a+n+1,cmp);
maxr[1]=a[1].b;
f[a[1].c]=1;
for (int i=2;i<=n;i++)
{
int mid,t=a[i].b,l=1,r=i;
while (l<=r)
{
mid=(l+r)/2;
if (maxr[mid]<=t) r=mid-1;
if (maxr[mid]>t) l=mid+1;
}
maxr[l]=max(maxr[l],t);
f[a[i].c]=l;
}
for (int i=1;i<=n;i++)
printf ("%d\n",f[i]);
}
文章最后发布于: 2019-04-16 21:30:07
相关阅读
su username 与 su - username 的区别
su username ,切换后的环境变量大部分还是切换前用户的环境su - username ,切换后则完全切换到了目标用户的环境env 查看环境变量