輸入樣例
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
輸出樣例
5
主要是貪心思想，以結束時間從小到大排序，
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
#define l first
#define r second
const int N=110;
bool cmp(PII a,PII b)
{
return a.r<b.r;
}
int main(void)
{
int n;
while(~scanf("%d",&n),n)
{
PII s[N];
int res=0,temp=0;
for(int i=0;i<n;i++)
scanf("%d%d",&s[i].l,&s[i].r);
sort(s,s+n,cmp);
for(int i=0;i<n;i++)
{
if(s[i].l>=temp)
{
res++;
temp=s[i].r;
}
}
cout<<res<<endl;
}
}
主要是雙指標演算法，
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int main(void)
{
int T;
cin>>T;
while(T--)
{
int v,n;
scanf("%d%d",&v,&n);
int w[N];
for(int i=0;i<n;i++) scanf("%d",&w[i]);
sort(w,w+n);
int l=0,r=n-1,res=0;
int temp=w[l];
while(l<=r)
{
if(temp+w[r]>v) r--,res++;
else
{
res++;
r--;
l++;
}
}
cout<<res<<endl;
}
}
剛開始以為是dp，后來看能分割，就是典型的貪心，先選價值大的，
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
typedef pair<int,int> PII;
#define v first
#define w second
bool cmp(PII a,PII b)
{
return a.v>b.v;
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--)
{
int n,V;
scanf("%d%d",&n,&V);
PII k[N];
for(int i=0;i<n;i++)
scanf("%d%d",&k[i].v,&k[i].w);
sort(k,k+n,cmp);
int res=0,i=0;
while(V)
{
if(V>=k[i].w)
{
res+=k[i].w*k[i].v;
}
else
{
res+=k[i].v*V;
break;
}
V-=k[i].w;
i++;
}
cout<<res<<endl;
}
}
這個看起來很有值得討論的地方，
首先我們可以根據輾轉相除法可以求出n,n+1的最大公約數為1所以呢，相鄰的兩個數公約數一定是1，那么最有可能產生公約數大于1的地方就是n,n+2,用輾轉相除法發現，要是奇數一定最大公約數為1（相鄰的奇數最大公約數為1），偶數最大公約數一定是2（不會有更大的了），然后這就出來了要是偶數我們就不選最大的三個數因為出現了最大公約數，我們要選互質最大，只能選n*(n-1)(n-3),但是我們好像也發現一個問題，就是要是n%3==0,n-3也必然被3整除，我們要選再下一位，再下一位就是n-4也是偶數，所以再選下一位n-5,就變成了n(n-1)(n-5),一看不大靠譜，我們是不是可以選擇(n-1) (n-2)(n-3),這個可以證明后者比較大的，（同時除以n-1,左邊是n2-5n,右邊是n2-5n+6)
思路就出來了，代碼如下，
#include<iostream>
using namespace std;
int main(void)
{
long long n,res;
cin>>n;
if(n&1) res=n*(n-1)*(n-2);
else
{
if(n%3==0)
res=(n-1)*(n-2)*(n-3);
else
res=n*(n-1)*(n-3);
}
cout<<res;
}
2655
這個很有難度，我們列舉每個點能不能作為最小的距離試一下，有點列舉了，然后再貪心，
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1e6+10;
int x[N],y[N],ans[N],l[N];
int main(void)
{
int n;
cin>>n;
memset(l,0x3f3f3f3f,sizeof l);
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
ans[k]=abs(x[k]-x[i])+abs(y[k]-y[j]);
sort(ans+1,ans+n+1);
int sum=0;
for(int k=1;k<=n;k++)
{
sum+=ans[k];
l[k]=min(l[k],sum);
}
}
for(int i=1;i<=n;i++)
cout<<l[i]<<endl;
}
查重？？我也很無奈，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258095.html
標籤：其他
上一篇：Codeforces Round #700 (Div. 2)-A. Yet Another String Game-題解--三目運算子
下一篇：【C語言】貪吃蛇小游戲代碼詳解