https://atcoder.jp/contests/abc297/tasks/abc297_d
D - Count Subtractions
题目大意：
给定一个n和一个m，每次如果n>m,n-=m;如果n<m,m-=n;
问我们多少次操作才能使n=m?
Sample Input 1
3 8
Sample Output 1
4
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=1e6+10,M=4023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
LL n,m;
cin>>n>>m;
LL sum=0;
while(n!=m)
{
if(n>m)
{
LL k=n/m;
sum+=n/m;
if(n%m==0)
{
sum--;
break;
}
n-=k*m;
}
else if(n<m)
{
LL k=m/n;
sum+=m/n;
if(m%n==0)
{
sum--;
break;
}
m-=k*n;
}
}
cout<<sum<<endl;
}
return 0;
}
E - Kth Takoyaki Set
https://atcoder.jp/contests/abc297/tasks/abc297_e
题目大意：
N种物品，第I种ai日元。物品可以重复购买。
求可能支付的第K个最低价。
Sample Input 1
4 6
20 25 30 100
Sample Output 1
50
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=1e6+10,M=4023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL a[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
LL n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
set<LL> st;
for(int i=1;i<=m;i++)
{
LL sum=*st.begin();
st.erase(sum);
for(int j=1;j<=n;j++)
{
st.insert(a[j]+sum);
}
}
cout<<*st.begin()<<endl;
}
return 0;
}