A. Hard Way
题目链接
给出三角形的三个顶点，问有最多多长的距离，使得无法直接从x轴沿直线且不穿过三角形内部到达。
思路：很容易得出仅当一条边是平行于x轴且三角形另一点在这条边下面才无法到达。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
struct node
{
double x,y;
} e[4];
bool cmp(node a,node b)
{
return a.y>b.y;
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>t;
while(t--)
{
for(int i=1;i<=3;i++)
cin>>e[i].x>>e[i].y;
sort(e+1,e+4,cmp);
bool flag=false;
if(e[1].y==e[2].y&&e[3].y<e[1].y||e[2].y==e[3].y&&e[1].y<e[2].y)
flag=true;
if(flag)
{
if(e[1].y==e[2].y)
printf("%.13lf\n",abs(e[1].x-e[2].x));
else
printf("%.13lf\n",abs(e[3].x-e[2].x));
}
else printf("0.0000000000000\n");
}
return 0;
}
B. Power Walking
题目链接
有n个电池，分给k个小朋友，每人至少一个，每个小朋友手中不同电池的种类数是属于本人的力量，问k个人力量最小的和是多少。
思路：仅有一个人时，最少就是所有电池种类和；两个人时，最少情况应该是分给该小朋友一个仅有一个的种类的电池，这样总的和不变；以此类推，当人数小于等于电池的种类数时，总的和就是电池种类数，大于时和就是人数。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n,x;
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>t;
while(t--)
{
cin>>n;
set<int>ss;
for(int i=1;i<=n;i++)
{
cin>>x;
ss.insert(x);
}
int sum=ss.size();
for(int i=1;i<=n;i++)
{
if(i<=sum) cout<<sum<<' ';
else cout<<i<<' ';
}
cout<<'\n';
}
return 0;
}
C. Great Sequence
题目链接
问最少加入几个数字，使得原数组可以分为若干个二元组，且满足第一个数乘x等于第二个数。
思路：排序，贪心思想，按照升序，若set中存在该数乘x的值，分别减去；若没有，则添加一个数。
tip：multiset：按顺序存储元素，与set不同的是，multiset可以存储重复元素；这里遍历用的是s.begin()，处理完一个元素erase一个。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+5;
ll k,x;
int t,n;
multiset<ll>s;
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
scanf("%d",&t);
while(t--)
{
scanf("%d%lld",&n,&x);
for(int i=1;i<=n;i++)
{
scanf("%lld",&k);
s.insert(k);
}
int ans=0;
while(s.size())
{
k=(*s.begin());
if(s.find(x*k)!=s.end())
{
s.erase(s.begin());
s.erase(s.find(x*k));
}
else
{
s.erase(s.begin());
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
|