CF1601D Difficult Mountain
自己的sb想法：
-
直接按 \(a\) 排序，能上就上，显然假了，第三个样例都过不去。
-
先让第一个能上去的且 \(a\) 最小的上去，然后去找第一个比当前攀登难度大的，相同的选 \(a\) 最小的，显然也假了。
牛逼贪心题。
以 \(\max(a_{i},s_{i})\) 为第一关键字， \(s_{i}\) 为第二关键字从小到大排序。
然后依次枚举，能选就选，就是最优答案。
证明：
按 \(\max(a,s)=a/s\) 分类讨论。
-
\(\max_{i}=a_{i},\max_{j}=a_{j}\) ，不妨设 \(a_{i}
-
\(\max_{i}=a_{i},\max_{j}=s_{j}\) ，如果 \(a_{i}>s_{j}\) 则同上， \(i\) 先上， \(j\) 一定上不去，所以不如让 \(j\) 先去试试。 如果 \(a_{i}\le s_{j}\) ，那么 \(i\) 先上对 \(j\) 显然不会有影响。
-
\(\max_{i}=s_{i},\max_{j}=s_{j}\) ，不妨设 \(s_{i}
取等类似，此处不再展开。
Code
#include
#include
#include
#include
using std::max;
using std::sort;
#define re register
const int MAX = 5e5+3;
#define long long long
#define scanf oma=scanf
#define freopen file freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
templateinline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int ans;
int n,d;
struct data
{
int s,a;
inline friend bool operator <(const data &x,const data &y)
{ return max(x.s,x.a)==max(y.s,y.a)?x.s signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); freopen("my.out","w",stdout);
#endif
cin >> n >> d;
for(re int i=1; i<=n; i++)
{ cin >> p[i].s >> p[i].a; }
sort(p+1,p+1+n);
for(re int i=1; i<=n; i++)
{
if(d<=p[i].s)
{ ans++,d = max(d,p[i].a); }
}
printf("%d\n",ans);
return 0;
};
};
signed main()
{ return OMA::main(); }