20200807 贪心;排队接水;[AHOI2018初中组]分组;国王的游戏
记录巧妙思维[自己写的太常规了就不放了]
排队接水|来源
有一个巧妙的存数据方式来输出排序之后编号的顺序(针对快排懒得用结构体的同学)
因为n<=1000，所以给每个ti都*1001，在加上当前序号，可以保证排序的时候序号不干扰排序，又可以方便输出序号（只需mod1001输出序号，／1001 输出时间）直达
[AHOI2018初中组]分组|来源
如果右边一列的高度不低于当前列，则连接右边一列最下方的方块。反之，停止画线。
这样，最靠左的一个“峰”相较其右边一列的高度差就不断减小，直到相同。如此反复。记录所画所有线的最短长度，即为答案。直达
国王的游戏|链接
用冒泡排序的思想优化排序直达
还没AC呢，等会看看哪错了
谁能想到是进位不够呢
其他看了的东西也一起记录一下叭不然就像啥也没学一样
Markdown入门教程
这个感觉不是很全，但是基本的语法差不多都有Git/Github入门
- 直接用命令行
- 可视化界面
其实熟悉了命令行也用不上可视化外包了
// main.cpp
// Water containing
//
// Created by Leonardo Cullen on 2017/5/6.
// Copyright © 2017年 Leonardo Cullen. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double sum;
long int n;
long long int t[1001];
double ans;
int main(int argc, const char * argv[])
{
cin>>n;
int x;
for(int i=1;i<=n;i++)
{
cin>>x;
t[i]=x*1001+i;
}
sort(t+1,t+1+n);
for(int j=1;j<=n;j++)
{
cout<<t[j]%1001<<" ";
sum+=t[j]/1001*(n-j);
}
cout<<endl;
ans=sum/n;
printf("%0.2lf",ans);
return 0;
}
#include<cstdio>
#include<map>
std::map<int,int>m;
typedef std::map<int,int>::iterator it;
int main(){
int n,ans=0x3f3f3f3f;
scanf("%d",&n);
for(int i=0;i<n;++i){
int t;
scanf("%d",&t);
++m[t];
//记录图像。
}
while(!m.empty()){
it i=m.begin(),j=m.begin();
--(*i).second;
int t=1;
for(++j;j!=m.end()&&(*j).first==(*i).first+1&&(*j).second>(*i).second;++i,++j){
++t;
--(*j).second;
}
//若 i,j 所对应的能力值是连续的，且 i 对应的那一列高度不高于 j，则继续画线。
i=m.begin();
while(i!=m.end()&&(*i).second==0){
m.erase((*i++).first);
}
//高度降为 0 后直接删除，便于计算。
if(t<ans){
ans=t;
}
//记录答案。
}
printf("%d",ans);
return 0;
}
#include <bits/stdc++.h>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<29)
#define make_pair mp
const int maxn=1e4+5;
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct node{
int left,right;
}a[maxn];
int cmp(node a,node b){
return a.right*a.left<b.right*b.left;
}
int maxs[maxn]={0},last[maxn];//前一位的乘积,从1开始算
int laaa_len=1,maaa_len=1;//前一位的位数
void ppl(int n){
int num=a[n-1].left,pp[maxn];//当前可获金币数量
memset(pp,0,sizeof(pp));
laaa_len+=10;//最多乘10^4,多加一位//实际上这里要多加，至于为什么，咱也不知道
rep(i,1,laaa_len)
{
pp[i]+=last[i]*num;
pp[i+1]+=pp[i]/10;
pp[i]%=10;
// cout<<pp[i]<<" "<<pp[i+1]<<endl;
}
while(!pp[laaa_len])laaa_len--;//获取当前位数
memcpy(last,pp,sizeof(pp));//获取当前乘积
// per(i,laaa_len,1)cout<<pp[i];
// cout<<endl;
//
num=a[n].right;
per(i,laaa_len,1)
{
pp[i-1]+=pp[i]%num*10;
pp[i]/=num;
}
while(!pp[laaa_len])laaa_len--;
// cout<<"num: "<<num<<' '<<endl;
// per(i,laaa_len,1)cout<<pp[i];
// cout<<endl;
//
per(i,laaa_len+2,1)
{
if(pp[i]==maxs[i]){continue;}
else if(pp[i]>maxs[i]){memcpy(maxs,pp,sizeof(pp));maaa_len=laaa_len;break;}
else break;
}
}
int main()
{
int n=read();n+=1;
rep(i,1,n){
a[i].left=read();a[i].right=read();
}
sort(a+2,a+n+1,cmp);
memset(last,0,sizeof(last));last[1]=1;
rep(i,2,n)ppl(i);
per(i,maaa_len,1)cout<<maxs[i];
return 0;
}
//指针
